#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int kthP(int k) {
    vector<bool> p(10000, true);
    p[0] = p[1] = false;
    vector<int> ps;
    for (int i = 2; i < 10000; i++) {
    if (p[i]) {
    ps.push_back(i);
    for (int j = i * 2; j < 10000; j += i)
    p[j] = false;
        }
    }
    return ps[k - 1];
}

int bfs(int s, vector<vector<int>> &adj, vector<bool> &vis) {
    queue<int> q;
    q.push(s);
    vis[s] = true;
    int c = 0;
    while (!q.empty()) {
    int u = q.front();
    q.pop();
    c++;
    for (int v : adj[u]) {
    if (!vis[v]) {
    vis[v] = true;
    q.push(v);
            }
        }
    }
    return c;
}
int main() {
    int a, b;
    cin >> a >> b;
    vector<vector<int>> adj(a + 1);
    for (int i = 0; i < b; i++) {
        int c, d;
        cin >> c >> d;
        adj[c].push_back(d);
        adj[d].push_back(c);
    }

    vector<bool> vis(a + 1, false);
    int mx = 0;
    for (int i = 1; i <= a; i++) {
    if (!vis[i]) {
    mx = max(mx, bfs(i, adj, vis));
        }
    }

    cout << mx << " " << kthP(mx) << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
class SegmentTree {
private:
    vector<ll> t;
    ll n;
    void upd(ll i, ll v, ll x, ll s, ll e) {
        if (s == e) {
            t[x] += v;
        } else {
            ll m = (s + e) / 2;
            if (i <= m) {
                upd(i, v, 2 * x, s, m);
            } else {
                upd(i, v, 2 * x + 1, m + 1, e);
            }
            t[x] = t[2 * x] + t[2 * x + 1];
        }
    }
    ll qry(ll l, ll r, ll x, ll s, ll e) {
        if (r < s || e < l) return 0;
        if (l <= s && e <= r) return t[x];
        ll m = (s + e) / 2;
        ll left = qry(l, r, 2 * x, s, m);
        ll right = qry(l, r, 2 * x + 1, m + 1, e);
        return left + right;
    }

public:
    SegmentTree(ll sz) : n(sz) {
        t.resize(4 * n, 0);
    }

    void upd(ll i, ll v) {
        upd(i, v, 1, 0, n - 1);
    }

    ll qry(ll l, ll r) {
        return qry(l, r, 1, 0, n - 1);
    }
};

vector<ll> solve(ll n, vector<ll>& a, ll q, vector<ll>& qrs) {
    vector<ll> res;
    SegmentTree st(n);
    vector<ll> b = a;
    sort(b.begin(), b.end());
    unordered_map<ll, ll> mp;
    for (ll i = 0; i < n; ++i) mp[b[i]] = i;

    auto cnt_inv = [&]() -> ll {
        ll inv = 0;
        for (ll i = n - 1; i >= 0; --i) {
            ll idx = mp[a[i]];
            inv += st.qry(0, idx - 1);
            st.upd(idx, 1);
        }
        for (ll i = 0; i < n; ++i) {
            st.upd(mp[a[i]], -1);
        }
        return inv;
    };

    for (ll x : qrs) {
        reverse(a.begin(), a.begin() + x);
        res.push_back(cnt_inv());
    }
    return res;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
int main(){
     int n;
     cin>>n;
     vector<int>arr(n);
     for(int i=0;i<n;i++)cin>>arr[i];
     vector<int>presum(n);
     presum[0]=arr[0];
     for(int i=1;i<n;i++)presum[i]=presum[i-1]+arr[i];
     vector<int>dp(n); 
     vector<int>val(n);
     dp[0]=1;
     val[0]=arr[0];

     for(int i=1;i<n;i++){
        
        int l=0,h=i;
        int ind=0;
        while(h>=l){
          int mid=(l+h)/2;
          int sum= presum[i]- (mid>0?presum[mid-1]:0);
          int prev = (mid>0?val[mid-1]:0);
          if(sum>=prev){
            ind=mid;
            l=mid+1;
          }
          else h=mid-1;
        }
        if(ind==0){
          dp[i]=1;
          val[i]=presum[i];
        }
        else{
          dp[i]=dp[ind-1]+1;
          val[i]=presum[i]-presum[ind-1];
        }
     }
     cout<<dp.back();
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll solve(ll n, ll m, vector<vector<string>>& c) {
    vector<vector<ll>> g1(n), g2(n);
    vector<ll> d1(n, 0), d2(n, 0);
    for (const auto& t : c) {
    if (t[0] == "x") {
    ll a = stoll(t[1]) - 1;
    ll b = stoll(t[2]) - 1;
    g1[a].push_back(b);
    d1[b]++;
    } else if (t[0] == "y") {
    ll a = stoll(t[1]) - 1;
    ll b = stoll(t[2]) - 1;
    g2[a].push_back(b);
    d2[b]++;
        }
    }

    auto ts = [&](vector<vector<ll>>& g, vector<ll>& d) -> vector<ll> {
    queue<ll> q;
    for (ll i = 0; i < n; i++) {
    if (d[i] == 0) q.push(i);
    }
    vector<ll> o;
    while (!q.empty()) {
    ll u = q.front();
    q.pop();
    o.push_back(u);
    for (ll v : g[u]) {
    d[v]--;
    if (d[v] == 0) q.push(v);
        }
        }
    return o.size() == n ? o : vector<ll>();
    };

    vector<ll> o1 = ts(g1, d1);
    vector<ll> o2 = ts(g2, d2);
    if (o1.empty() || o2.empty()) return -1;
    vector<ll> r(n, 0), cols(n, 0);
    for (ll i = 0; i < n; i++) {
    for (ll v : g1[o1[i]]) {
    r[v] = max(r[v], r[o1[i]] + 1);
    }
    }
    for (ll i = 0; i < n; i++) {
    for (ll v : g2[o2[i]]) {
    cols[v] = max(cols[v], cols[o2[i]] + 1);
        }
    }
    ll max_r = *max_element(r.begin(), r.end()) + 1;
    ll max_cols = *max_element(cols.begin(), cols.end()) + 1;
    return max_r + max_cols;
}
int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<string>> c(m, vector<string>(3));
    for (ll i = 0; i < m; i++) {
        cin >> c[i][0] >> c[i][1] >> c[i][2];
    }
    cout << solve(n, m, c) << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll maxcoins(ll A[], ll siz) {
    ll nums[siz + 2];
    ll n = 1;
    for (ll i = 0; i < siz; i++) {
    if (A[i] > 0) {
    nums[n] = A[i];
    n++;
    }
    }
    nums[0] = nums[n] = 1;
    n++;
    ll dp[n][n] = {};
    for (ll j = 2; j < n; j++) {
    for (ll left = 0; left < n - j; left++) {
    ll right = left + j;
    for (ll i = left + 1; i < right; i++) {
    if (left == 0 && right == n - 1)
    dp[left][right] = max(nums[left] * nums[i] * nums[right] + dp[left][i] + dp[i][right], dp[left][right]);
    else
    dp[left][right] = max(nums[left] * nums[right] + dp[left][i] + dp[i][right], dp[left][right]);
            }
        }
    }

    return dp[0][n - 1];
}

int main() {
    ll T;
    cin >> T;
    for (ll t = 1; t <= T; t++) {
    ll siz;
    cin >> siz;
    ll A[siz];
    for (ll i = 0; i < siz; i++) {
    cin >> A[i];
    }
    ll ans = maxcoins(A, siz);
    cout << "#" << t << ans << endl;
    }

    return 0;
}

using namespace std;

#define ll long long

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

    vector<pair<int, int>> bombTimers(numBombs);
    for (int i = 0; i < numBombs; i++)
        cin >> bombTimers[i].first >> bombTimers[i].second;

    sort(bombTimers.begin(), bombTimers.end(), [](const auto &a, const auto &b) {
        return a.second < b.second;
    });

    ll currentTime = 0;
    for (int i = 0; i < numBombs; i++) {
        currentTime += bombTimers[i].first;
        if (currentTime > bombTimers[i].second) {
            cout << -1 << endl;
            return 0;
        }
    }

    cout << currentTime << endl;
    return 0;
}