using namespace std;
using ii = pair<int, int>;
using ll = long long;
int main(void)
{
    int n, m, ai;
    cin >> n >> m;
    multiset<int> a;
    for (int i = 0; i < n; ++i)
        cin >> ai, a.insert(ai);
    vector<ii> queries;
    queries.resize(m);
    for (auto &[ci, bi] : queries)
        cin >> bi >> ci;
    sort(queries.begin(), queries.end(), greater<ii>());
    for (auto [ci, bi] : queries)
    {
        if (*a.begin() >= ci)
            break;
        while (bi--)
        {
            auto it = a.begin();
            if (*it >= ci)
                break;
            a.erase(it);
            a.insert(ci);
        }
    }
    cout << accumulate(a.begin(), a.end(), (ll)0);
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vii = vector<ii>;
int const NMAX = 1e5 + 11;
int n, color[NMAX];
vii g[NMAX];
void dfs(int u, int p = -1, int d = 0)
{
    color[u] = d;
    for (auto [v, c] : g[u])
    {
        if (v == p)
            continue;
        dfs(v, u, (d + c) % 2);
    }
}
int main(void)
{
    int u, v, c;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v >> c, --u, --v;
        g[u].emplace_back(v, c);
        g[v].emplace_back(u, c);
    }
    dfs(0);
    for_each(color, color + n, [](int x) { cout << x << endl; });
    return 0;
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
int gcd(int a, int b) { return (b == 0 ? a : gcd(b, a % b)); }
struct segment_tree
{
    int n;
    vi t;
    segment_tree(vi const &a)
    {
        n = (int)a.size();
        t.resize(4 * n);
        build(a, 1, 0, n - 1);
    }
    inline int left(int v) { return 2 * v; }
    inline int right(int v) { return 2 * v + 1; }
    int merge(int a, int b) { return gcd(a, b); }
    void build(vi const &a, int v, int tl, int tr)
    {
        if (tl == tr)
            t[v] = a[tl];
        else
        {
            int tm = (tl + tr) / 2;
            build(a, left(v), tl, tm);
            build(a, right(v), tm + 1, tr);
            t[v] = merge(t[left(v)], t[right(v)]);
        }
    }
    int query(int ql, int qr) { return query_util(1, 0, n - 1, ql, qr); }
    int query_util(int v, int tl, int tr, int ql, int qr)
    {
        if (ql == tl and qr == tr)
            return t[v];
        else if (ql > qr)
            return 0;
        else
        {
            int tm = (tl + tr) / 2;
            return merge(query_util(left(v), tl, tm, ql, min(tm, qr)),
                         query_util(right(v), tm + 1, tr, max(ql, tm + 1), qr));
        }
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n);
    read_n(a.begin(), n);
    segment_tree seg(a);
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int l = 0, r = 0;
        if (i > 0)
            l = seg.query(0, i - 1);
        if (i < n - 1)
            r = seg.query(i + 1, n - 1);
        ans = max(ans, gcd(r, l));
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
int const HMAX = 200 + 11;
int const DMAX = 10;
int const INF = 1e9;
int c[DMAX][DMAX], a[HMAX][HMAX], dist[DMAX][DMAX];
void floyd_warshall(void)
{
    for (int i = 0; i < DMAX; i++)
    {
        for (int j = 0; j < DMAX; j++)
        {
            if (i == j)
                dist[i][j] = 0;
            else if (c[i][j])
                dist[i][j] = c[i][j];
            else
                dist[i][j] = INF;
        }
    }
    for (int k = 0; k < DMAX; k++)
    {
        for (int i = 0; i < DMAX; i++)
        {
            for (int j = 0; j < DMAX; j++)
            {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}
int main(void)
{
    int h, w, ai;
    cin >> h >> w;
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            cin >> c[i][j];
    floyd_warshall();
    int ans = 0;
    for (int i = 0; i < h; ++i)
    {
        for (int j = 0; j < w; ++j)
        {
            cin >> ai;
            if (ai == -1 or ai == 1)
                continue;
            ans += dist[ai][1];
        }
    }
    cout << ans << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
int main(void)
{
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    int k = -1;
    bool ok;
    if (n < m)
    {
        cout << "UNRESTORABLE" << endl;
        return 0;
    }
    for (int i = 0; i < n - m + 1; ++i)
    {
        ok = true;
        for (int j = 0; j < m; ++j)
        {
            if (s[i + j] != t[j] and s[i + j] != '?')
            {
                ok = false;
            }
        }
        if (ok)
            k = i + m - 1;
    }
    if (k != -1)
    {
        for (int i = 0; i < n; ++i)
        {
            if (i >= k - m + 1 and i <= k)
            {
                cout << t[i - k + m - 1];
            }
            else
            {
                if (s[i] == '?')
                    cout << 'a';
                else
                    cout << s[i];
            }
        }
    }
    else
        cout << "UNRESTORABLE" << endl;
    return 0;
}

using namespace std;
using vi = vector<int>;
using ll = long long;
int const NMAX = 200 + 11;
ll const INF = 1e15;
int n, m, g[NMAX][NMAX];
ll dist[NMAX][NMAX];
void floyd_warshall(void)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                dist[i][j] = 0;
            else if (g[i][j])
                dist[i][j] = g[i][j];
            else
                dist[i][j] = INF;
        }
    }
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}
int main(void)
{
    int rn, u, v, c;
    vi r;
    cin >> n >> m >> rn;
    r.resize(rn);
    for (auto &ri : r)
        cin >> ri;
    while (m--)
    {
        cin >> u >> v >> c;
        g[u][v] = g[v][u] = (g[u][v] == 0 ? c : min(g[u][v], c));
    }
    sort(r.begin(), r.end());
    floyd_warshall();
    ll ans = INF, cur;
    do
    {
        cur = 0;
        for (int i = 1; i < rn; ++i)
            cur += dist[r[i - 1]][r[i]];
        ans = min(ans, cur);
    } while (next_permutation(r.begin(), r.end()));
    cout << ans << endl;
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using ll = long long;
int const NMAX = 1e5 + 11;
int n;
ll dist[NMAX];
vector<ii> g[NMAX];
void dfs(int u, int p = -1, ll d = 0)
{
    dist[u] = d;
    for (auto [v, c] : g[u])
        if (v != p)
            dfs(v, u, d + c);
}
int main(void)
{
    int q, k, u, v, c;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v >> c, u--, v--;
        g[u].emplace_back(v, c);
        g[v].emplace_back(u, c);
    }
    cin >> q >> k, k--;
    dfs(k);
    while (q--)
    {
        cin >> u >> v, u--, v--;
        cout << dist[u] + dist[v] << endl;
    }
    return 0;
}

using namespace std;
bool equal(string const &s, int m)
{
    for (int i = 0; i < m / 2; ++i)
        if (s[i] != s[i + m / 2])
            return false;
    return true;
}
int solve(string const &s)
{
    int n = s.size();
    for (int i = n - 2; i > 0; i -= 2)
    {
        if (equal(s, i))
            return i;
    }
    return 0;
}
int main(void)
{
    string s;
    cin >> s;
    cout << solve(s) << endl;
    return 0;
}

using namespace std;
int const NMAX = 1e5 + 11;
int n, succ[NMAX];
bool vis[NMAX];
int dfs(int u)
{
    if (u == 1)
        return 0;
    int ans = -1;
    int v = succ[u];
    vis[u] = true;
    if (not vis[v])
        ans = dfs(v);
    if (ans != -1)
        ++ans;
    return ans;
}
int main(void)
{
    int n;
    cin >> n;
    for (int u = 0; u < n; ++u)
        cin >> succ[u], --succ[u];
    cout << dfs(0) << endl;
    return 0;
}

using namespace std;
int main(void)
{
    int n, m, u, v;
    cin >> n >> m;
    vector<int> deg(n, 0);
    while (m--)
    {
        cin >> u >> v, --u, --v;
        deg[u]++, deg[v]++;
    }
    for_each(deg.begin(), deg.end(), [](int x) { cout << x << endl; });
    return 0;
}