Problem: Example

Input

2 5 4
5 7
4 8


Output

8 7

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 155

int N;
ll A,B;

struct Info{
	ll nut_value,sweet_value;
};
Info info[NUM];
ll sweet_sum;
ll dp[NUM][NUM];

ll get_max(int index, ll diff){

	ll ret = 0;

	ll left = 0,right = sweet_sum,mid = (left+right)/2;

	while(left <= right){

		if(dp[index][mid] <= diff){

			ret = mid;
			left = mid+1;
		}else{
			right = mid-1;
		}
		mid = (left+right)/2;
	}

	return ret;
}

bool can_get(int index,ll diff,ll tmp_sweet_sum){

	ll eat_value = sweet_sum-get_max(index+1,-(diff+info[index].nut_value));
	ll not_value;

	if(diff > 0){

		not_value = get_max(index+1,diff-1-info[index].nut_value);

	}else{

		not_value = 0;
	}

	return tmp_sweet_sum <= max(0ll,max(eat_value,not_value));
}


int main(){

	scanf("%d %lld %lld",&N,&A,&B);

	sweet_sum = 0;

	for(int i = 0; i < N; i++){

		scanf("%lld %lld",&info[i].nut_value,&info[i].sweet_value);
		sweet_sum += info[i].sweet_value;
	}

	for(int i = 0; i <= N; i++){
		dp[i][0] = 0;
		for(int k = 1; k <= sweet_sum; k++){
			dp[i][k] = HUGE_NUM;
		}
	}

	sweet_sum = 0;
	ll left,right,mid,min_diff;

	for(int i = N-1; i >= 0; i--){

		sweet_sum += info[i].sweet_value;

		for(int tmp_sweet = 0; tmp_sweet <= sweet_sum; tmp_sweet++){

			left= -HUGE_NUM,right = HUGE_NUM,mid = (left+right)/2;
			min_diff = HUGE_NUM;

			while(left <= right){
				if(can_get(i,mid,tmp_sweet)){

					min_diff = mid;
					right = mid-1;

				}else{

					left = mid+1;
				}
				mid = (left+right)/2;
			}
			dp[i][tmp_sweet] = min_diff;
		}
	}

	ll ans_A = get_max(0,A-B);
	ll ans_B = sweet_sum-ans_A;

	printf("%lld %lld\n",ans_A,ans_B);

	return 0;
}