Problem: Example

Input

2 5 4
5 7
4 8


Output

8 7

Solution (in CPP):

Solution:
#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> i_i;
struct edge { int v, w; };

ll INF = LLONG_MAX / 2;

int main() {
	int N, A, B; cin >> N >> A >> B;
	vector<int> r(N), s(N);
	int M = 0;
	for (int i = 0; i < N; i++) {
		cin >> r[i] >> s[i];
		M += s[i];
	}
	int lb = 0, ub = M + 1;
	while (ub - lb > 1) {
		int mid = (lb + ub) / 2;
		vector<vector<ll> > dp(2, vector<ll>(M + 1));
		for (int t = 0; t <= 1; t++)
			for (int x = 0; x <= M; x++)
				dp[t][x] = (x >= mid ? -INF : INF);
		for (int i = N - 1; i >= 0; i--) {
			vector<vector<ll> > _dp(2, vector<ll>(M + 1));
			for (int x = 0; x <= M; x++) {
				_dp[0][x] = INF;
				if (x + s[i] <= M)
					_dp[0][x] = min(_dp[0][x], dp[1][x + s[i]] - r[i]);
				_dp[0][x] = min(_dp[0][x], max(1LL, dp[0][x] + r[i] + 1));
			}
			for (int x = 0; x <= M; x++) {
				_dp[1][x] = -INF;
				_dp[1][x] = max(_dp[1][x], dp[0][x] + r[i]);
				if (x + s[i] <= M)
					_dp[1][x] = max(_dp[1][x], min(-1LL, dp[1][x + s[i]] - r[i] - 1));
			}
			dp = _dp;
		}
		if (dp[0][0] <= A - B) lb = mid;
		else ub = mid;
	}
	cout << lb << ' ' << M - lb << endl;
}