ZZULIOJ 2829: 闯关游戏

题目描述
小i正在玩一个闯关游戏，游戏一共n关。
初始的时候小i有H点体力以及0个金币。
小i只能按从第1关到第n关按顺序完成。在第i关时，小i要在三种操作中选择一种：
1.当前体力不小于Ai可以选择这个操作，消耗Ai点体力，获得Bi个金币。
2.当前体力不小于Ci可以选择这个操作，消耗Ci点体力，获得Di个金币。
3.结束游戏，直接结算。
当小i完成全部n个关卡后会自动结束游戏，进行结算。
结算时小i最多获得了多少金币？
输入
第一行一个正整数T表示数据组数。
对于每组数据，第一行输入两个正整数n,H，分别表示关卡数量和初始体力值。
接下来n行，每行输入4个正整数Ai,Bi,Ci,Di。
T≤2000,1≤n,H,Ai,Bi,Ci,Di≤6000,∑n+H≤150000,仅有6组数据满足n,H>100
输出
对于每组数据输出一行，表示小i最多能得到多少金币。
样例输入 Copy
2
2 8
2 2 1 2
1 4 3 3
4 9
3 1 3 2
2 2 2 2
4 3 3 1
2 4 2 1

样例输出 C

ZZULIOJ 2829: 闯关游戏最先出现在Python成神之路。