Problem: Example

Input

2 5 4
5 7
4 8


Output

8 7

Solution (in CPP):

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

typedef long long ll;
const ll kInf = 1LL << 50;
const int kMax = 150;

int N, Si[kMax];
ll A, B, Ri[kMax];

int sum;
ll f[2][kMax + 1][kMax + 1];
bool fv[2][kMax + 1][kMax + 1];

void read();
void solve();

ll dp(int, int, int);

int main() {
	while (cin >> N >> A >> B)
		read(), solve();
	
	return 0;
}

void read() {
	for (int i = 0; i < N; ++i)
		cin >> Ri[i] >> Si[i];
}

void solve() {
	int res;
	
	sum = accumulate(&Si[0], &Si[N], 0);
	fill(&fv[0][0][0], &fv[2][0][0], false);
	for (res = sum; res > 0; --res)
		if (dp(0, 0, res) <= A - B)
			break;
	cout << res << " " << sum - res << "\n";
}

ll dp(int p, int b, int s) {
	if (s < 0)
		return -kInf;
	
	if (s > sum)
		return kInf;
	
	if (fv[p][b][s])
		return f[p][b][s];
	
	fv[p][b][s] = true;
	if (b == N)
		return f[p][N][s] = (s == 0 ? -kInf : kInf);
	
	// alice
	if (p == 0) {
		f[0][b][s] = dp(0, b, s + 1);
		f[0][b][s] = min(f[0][b][s], dp(1, b + 1, s - Si[b]) - Ri[b]);
		f[0][b][s] = min(f[0][b][s], max(dp(0, b + 1, s) + Ri[b] + 1, 1LL));
	}
	// brianna
	else {
		f[1][b][s] = dp(1, b, s - 1);
		f[1][b][s] = max(f[1][b][s], dp(0, b + 1, s) + Ri[b]);
		f[1][b][s] = max(f[1][b][s], min(dp(1, b + 1, s - Si[b]) - Ri[b] - 1, 0LL));
	}
	
	return f[p][b][s];
}