#50. 鸡与地上城
鸡与地上城
题目描述
小又鸟正在挑战地上城,小又鸟的初始血量为 ,初始攻击力为 ,但是小又鸟很没有钱钱,初始小又鸟只有高达 个金币。
地上城中一共有 个怪物,挑战第 个怪物需要消耗 的血量,且至少需要 的攻击力,若血量或攻击力不足则无法挑战这个怪物,即当且仅当当前 , 才能挑战第 个怪物,挑战第 个怪物后得到的战利品会让小又鸟增加 的攻击力,并获得 个金币。
现在小又鸟要按顺序挑战地上城中的怪物,对于每个怪物,他可以选择挑战或放弃,求最后得到的金币最多为多少。当然,在挑战过程中,小又鸟的血量不能小于等于 。
输入格式
输入第一行三个整数 , , ,含义见题意。
接下来 行,每行四个整数 , , , ,含义见题意。
输出格式
输出一行一个整数,表示答案。
输入输出样例
输入 #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:
选择打败第 , , 个怪物是最优解,可以得到 枚金币,优于打败第 , , 个怪物得到的 枚金币。
对于样例 #2:
注意在挑战过程中小又鸟的血量不能小于等于 。
相关
在下列比赛中: