#50. 鸡与地上城

鸡与地上城

题目描述

小又鸟正在挑战地上城,小又鸟的初始血量为 healthhealth ,初始攻击力为 atkatk ,但是小又鸟很没有钱钱,初始小又鸟只有高达 00 个金币。

地上城中一共有 nn 个怪物,挑战第 ii 个怪物需要消耗 aia_i 的血量,且至少需要 bib_i 的攻击力,若血量或攻击力不足则无法挑战这个怪物,即当且仅当当前 health>aihealth > a_i , atkbiatk \geq b_i 才能挑战第 ii 个怪物,挑战第 ii 个怪物后得到的战利品会让小又鸟增加 cic_i 的攻击力,并获得 did_i 个金币。

现在小又鸟要按顺序挑战地上城中的怪物,对于每个怪物,他可以选择挑战或放弃,求最后得到的金币最多为多少。当然,在挑战过程中,小又鸟的血量不能小于等于 00

输入格式

输入第一行三个整数 nn , healthhealth , atkatk ,含义见题意。 (1n,health,atk400)(1 \leq n,health,atk \leq 400)

接下来 nn 行,每行四个整数 aia_i , bib_i , cic_i , did_i ,含义见题意。 (1ai,bi,ci400,1di109)(1 \leq a_i,b_i,c_i \leq 400,1 \leq d_i \leq 10^9)

输出格式

输出一行一个整数,表示答案。

输入输出样例

输入 #1

6 10 3
1 4 400 1000
5 2 2 1
2 3 1 3
2 6 2 7
3 4 4 3
4 8 5 4

输出 #1

11

输入 #2

2 3 2
2 2 2 1
3 1 1 2

输出 #2

1

说明与提示

对于样例 #1:

选择打败第 22 , 33 , 44 个怪物是最优解,可以得到 1+3+7=111+3+7=11 枚金币,优于打败第 33 , 55 , 66 个怪物得到的 3+3+4=103+3+4=10 枚金币。

对于样例 #2:

注意在挑战过程中小又鸟的血量不能小于等于 00