BZPRO
#5046. [Lydsy1709月赛]分糖果游戏
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
小Q与tangjz正在玩一个有趣的游戏。n块糖果从左往右排成一排，第i颗糖果的能量值为r_i，美味度为s_i。两个
人一开始的能量值分别为A和B，小Q先手，他们轮流做出行动，直到所有糖果都被取完。当前操作方每次可以做以
下两种选择中的一种：
1.不行动，并把机会交给对手，但这需要支付1点能量，如果当前剩余能量为0，则不可以不行动。
2.拿走最左边的糖果，再把机会交给对手，这不需要支付能量，同时还能补充拿走的糖果对应的能量值。
请写一个小Q和tangjz都想让自己拿到的糖果的美味度之和尽量大，他们都会以最佳策略进行游戏。
请写一个程序计算最终两人拿到糖果的美味度之和。
输入格式
第一行包含3个整数n,A,B(1<=n<=150,0<=A,B<=10^9)$，分别表示糖果的个数以及两人的初始能量。
接下来n行，每行两个整数r_i,s_i(0<=r_i<=10^9,0<=s_i<=150)，分别表示从左往右每个糖果的能量值和美味度。
输入数据保证s_1+s_2+...+s_n<=150。
输出格式
输出一行两个整数，分别表示小Q获得的糖果的美味度之和以及tangjz获得的糖果的美味度之和。
样例
样例输入
2 5 4
5 7
4 8
样例输出
8 7
数据范围与提示
BZPRO