#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int f[20][55][25][20][15];
int p[5] = { 0, 4, 6, 8, 5 };
int total = 19;

struct Res
{
    int a, b, c, d;
}res[15];

int main()
{
    int cnt = 1;
    for (int i = total / p[1]; i >= 0; i--)
    {
        for (int j = total / p[2]; j >= 0; j--)
        {
            for (int k = total / p[3]; k >= 0; k--)
            {
                for (int l = total / p[4]; l >= 0; l--)
                {
                    int sum = i * p[1] + j * p[2] + k * p[3] + l * p[4];
                    if (sum <= total)
                    {
                        if (total - sum < 4)
                        {
                            res[cnt].a = i;
                            res[cnt].b = j;
                            res[cnt].c = k;
                            res[cnt].d = l;
                            cnt++;
                        }
                    }
                }
            }
        }
    }
    //cout << cnt << endl;

    memset(f, 0x3f, sizeof f); // 初始化
    for (int i = 1; i < cnt; i++)
    {
        for (int j = 1; j < cnt; j++)
        {
            f[i][res[j].a][res[j].b][res[j].c][res[j].d] = 1;
            cout << i << " " << res[j].a << " " << res[j].b << " " << res[j].c << " " << res[j].d << endl;
        }
    }


    int ans = 1e9;
    for (int x1 = 1; x1 < cnt; x1++)
    {
        for (int x2 = x1 + 1; x2 < cnt; x2++)
        {
            for (int x3 = x2 + 1; x3 <= cnt; x3++)
            {
                for (int i = 0; i <= 50; i++)
                {
                    for (int j = 0; j <= 20; j++)
                    {
                        for (int k = 0; k <= 15; k++)
                        {
                            for (int l = 0; l <= 10; l++)
                            {
                                int& t = f[x1][i][j][k][l];
                                t = min({ t,
                                f[x1][i - res[x1].a][j - res[x1].b][k - res[x1].c][l - res[x1].d] + 1,
                                f[x2][i - res[x2].a][j - res[x2].b][k - res[x2].c][l - res[x2].d] + 1,
                                f[x3][i - res[x3].a][j - res[x3].b][k - res[x3].c][l - res[x3].d] + 1 });
                            }
                        }
                    }
                }
                ans = min(ans, f[x1][50][20][15][10]);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int N = 10, M = N * N / 2;
int p[7] = {0, 3, 9, 12, 5, 18, 4};
int h[N], ne[M], e[M], w[M], idx;
int dist[N];
int n;

void add(int a,int b,int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void build(int S6)
{
    memset(h,-1,sizeof h);    
    idx = 0;

    add(0, 6, S6), add(6, 0, -S6);
    for(int i = 2; i <= 6; i ++) add(i - 2, i, p[i]);
    for(int i = 1; i <= 1; i ++) add(4 + i, i, p[i] - S6);
    for(int i = 1; i <= 6; i ++) add(i - 1, i, 0);
}


bool spfa(int c)
{   //求最长路,判断正环
    queue<int> q;
    vector<bool> st(N, false);
    vector<int> cnt(N, 0);
    memset(dist, -0x3f, sizeof dist);
    build(c);

    //差分约束从源点出发
    q.push(0);
    st[0] = true;
    dist[0] = 0;

    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(cnt[j] >= 7) return false;
                if(!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return true;
}


int main()
{   
    int l = 0, r = INF;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (spfa(mid)) r = mid;
        else l = mid + 1;
    }
    if (r == INF) cout << "No Solution!" << endl;
    else cout << l << endl;
    return 0;
}

/* 1.分别计数 奇数和偶数的个数
   2.分类讨论：
   (1) 如果奇数个数和偶数个数相等, ans = 个数
   (2) 如果奇数的个数 - 偶数的个数 = c
   (3) 如果偶数的个数 - 奇数的个数 = c
   其中, 2个奇数可以凑成1个偶数, 因此答案为: 偶数的个数 + [c] / 3；如果有余数则向上取整
        但是多出的偶数没法通过加构成奇数, 因此答案为: 奇数个数
    */

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int odd = 0, even = 0;
    for (int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;

        if (x % 2 == 1) odd ++;
        else even ++; 
    }

    while (odd > even) odd -= 2, even ++;

    if (even >= odd + 1) cout << odd * 2 + 1 << endl;
    else if (even == odd) cout << 2 * odd << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 110;

int n, m;
int w[N], id[N];
bool st[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> w[i];
    for (int i = 0; i < m; i ++ )
    {
        cin >> id[i];
        st[id[i]] = true;
    }

    sort(id, id + m, [&](int a, int b) {
        return w[a] > w[b];
    });

    LL res = 0;
    for (int i = 1; i <= n; i ++ )
        if (!st[i])
            res += w[i];

    for (int i = 0; i < m; i ++ )
        res = max(res * 2, res + w[id[i]]);

    cout << res << endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <vector>
using namespace std;

#define int long long
#define endl '\n'

signed main()
{
    string s;
    cin >> s;

    set<int> st;
    for (int i = 0; i < s.size(); i ++) st.insert(s[i] - '0');

    if ((int)st.size() % 2 == 0) cout << "even" << endl;
    else cout << "odd" << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    int c, d, n, m, k;
    cin >> c >> d >> n >> m >> k;
    int cnt = n * m - k;
    if (cnt <= 0) puts("0");
    else
        cout << min({cnt * d, cnt / n * c + cnt % n * d, (cnt + n - 1) / n * c}) << endl;

    return 0;
}

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <set>
#include <map>
using namespace std;

#define int long long

signed main()
{
    int n;
    cin >> n;

    vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i ++) cin >> a[i];
    vector<int> sa(n + 1, 0);
    for (int i = 1; i <= n; i ++) sa[i] = sa[i - 1] + a[i];

    vector<int> b(a);
    sort(b.begin() + 1, b.end());
    vector<int> sb(n + 1, 0);
    for (int i = 1; i <= n; i ++) sb[i] = sb[i - 1] + b[i];

    int m;
    cin >> m;

    while (m --)
    {
        int id, l, r;
        cin >> id >> l >> r;

        if (id == 1) cout << sa[r] - sa[l - 1] << endl;
        else cout << sb[r] - sb[l - 1] << endl; 
    }

    return 0;
}

#include <iostream>
#include <map>
using namespace std;

map<int, int> mp;
int main()
{
    int n;
    cin >> n;


    int maxv = 0;
    while (n --)
    {
        int hour, minute;
        cin >> hour >> minute;
        int x = hour * 60 + minute;

        mp[x] ++;
        maxv = max(maxv, mp[x]);
    }

    cout << maxv << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

#define int long long
const int N = 1e5 + 10;
int p[N];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}


signed main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) p[i] = i;

    while (m -- )
    {
        int a, b;
        cin >> a >> b;

        int pa = find(a);
        int pb = find(b);

        if (pa != pb)
        {
            p[pa] = pb;
        }
    }

    int res = 1;
    for (int i = 1; i <= n; i ++)
    {
        if (p[i] != i)  res *= 2;
    }
    cout << res << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define int long long

signed main()
{
    string s;
    cin >> s;
    s = "?" + s;

    int n;
    cin >> n;

    vector<int> v(27, 0);
    int maxv = 0;
    for (int i = 0; i <= 26; i ++)
    {
        cin >> v[i];
        maxv = max(maxv, v[i]);
    }

    int res = 0;
    for (int i = 1; i < s.size(); i ++)
    {
        res += v[s[i] - 'a'] * i;
    }

    for (int i = s.size(); i < s.size() + n; i ++)
    {
        res += maxv * i;
    }

    cout << res << endl;

    return 0;
}