Problem: Example

Input

2 5 4
5 7
4 8


Output

8 7

Solution (in CPP):

Solution:
#include <vector>
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <cmath>
#include <complex>
#include <algorithm>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>
#include <valarray>
#include <list>

using namespace std;

typedef long long ll;

template<class T>
struct Pi {
    T x, y;
    Pi() {}
    Pi(T xx, T yy) {
        x = xx; y = yy;
    }
    bool operator<(const Pi &r) const {
        if (x != r.x) return x < r.x;
        return y < r.y;
    }
    bool operator>(const Pi &r) const {
        if (x != r.x) return x > r.x;
        return y > r.y;
    }
    bool operator==(const Pi &r) const {
        if (x != r.x) return false;
        return y == r.y;
    }
};

template<class T>
struct Ti {
    T x, y, z;
    Ti() {}
    Ti(T xx, T yy, T zz) {
        x = xx; y = yy; z = zz;
    }
    bool operator<(const Ti &r) const {
        if (x != r.x) return x < r.x;
        if (y != r.y) return y < r.y;
        return z < r.z;
    }
    bool operator>(const Ti &r) const {
        if (x != r.x) return x > r.x;
        if (y != r.y) return y > r.y;
        return z > r.z;
    }
    bool operator==(const Ti &r) const {
        if (x != r.x) return false;
        if (y != r.y) return false;
        return z == r.z;
    }
};

const int MN = 200;
const ll INF = 1LL<<50;

ll r[MN];
int s[MN], sum[MN];
ll dp[MN][MN];
bool used[MN][MN];

ll solve(int i, int ws) {
    if (i == -1) return INF;
    if (i == 0) {
        if (ws <= s[0]) return -INF;
        else return INF;
    }
    if (ws <= 0) return -INF;
    if (used[i][ws]) return dp[i][ws];
    used[i][ws] = true;

    ll res = 1-r[i]-solve(i-1, sum[i]-ws+1);
    res = min(res, max(1LL, 1+r[i]+solve(i-1, ws)));
    return (dp[i][ws] = res);
}

int main() {
    int n; ll a, b;
    cin >> n >> a >> b;
    for (int i = n-1; i >= 0; i--) {
        cin >> r[i] >> s[i];
    }
    sum[0] = s[0];
    for (int i = 1; i < n; i++) {
        sum[i] = sum[i-1] + s[i];
    }
    ll ad = a-b;
    ll ar = -1;
    for (int i = 0; i < MN; i++) {
        if (solve(n-1, i) <= ad) ar = i;
    }
    cout << ar << " " << sum[n-1]-ar << endl;
    return 0;
}