Problem: Example

Input

2 5 4
5 7
4 8


Output

8 7

Solution (in CPP):

Solution:

#include<bits/stdc++.h>
using namespace std;
#define D(x)		cout << #x " = " << (x) << endl
#define MAX 		150
typedef long long int LL; 

const LL inf = 1e16; 

int hap[MAX+5]; 
int enr[MAX+5]; 
int csum[MAX+5]; 
int n;
LL dp[MAX+5][MAX+5]; 

LL F(int i, int h){
	if(h <= 0) return -inf;
	
	if(i == n + 1){
		if(h <= 0) return -inf; 
		return inf;
	}
	
	if(dp[i][h] != -1) return dp[i][h]; 
	
	///I eat it
	int opHap = (csum[i + 1] - (h - hap[i])) + 1;
	LL eg = F(i + 1, opHap); 
	LL p = -eg + 1 - enr[i]; 
		
	
	///I don't eat it
	eg = F(i + 1, h);
	LL q = max(1LL, eg + enr[i] + 1);
		
	return dp[i][h] = min(p, q);    
}

int main()
{
	//freopen("in.txt", "r", stdin);
	
	int i, A, B;
	memset(dp, -1, sizeof(dp));
	
	scanf("%d %d %d", &n, &A, &B);
	for(i = 1; i <= n; i++){
		scanf("%d %d", &enr[i], &hap[i]); 
	}
	for(i = n; i >= 1; i--){
		csum[i] = hap[i] + csum[i + 1];
	}
	
	
	for(i = csum[1]; i >= 0; i--)
		if(F(1, i) <= A - B){
			printf("%d %d\n", i, csum[1] - i);
			return 0; 
		}
	return 0;
}