#P18403. Monster Generator
Monster Generator
Monster Generator
你正在玩一款与怪物战斗的电脑游戏。为了成为游戏中的高手,你决定从今天开始,使用怪物生成器训练,并在接下来的 天继续训练。
生成器每天产生 只怪物。假设现在是第 天(),你需要在战斗前设置初始生命值 ,随后以任意顺序击败当天生成的全部 只怪物。
与第 只怪物战斗时,你会先失去 点生命值;最终击败它后,再获得 点生命值作为奖励。
只要生命值变为负数(小于 0),当天训练就会失败。生命值恰好等于 0 是允许的。 即使击败怪物后会获得奖励,也不能在此前扣除生命值时变成负数。
无论上一天结束时还剩下多少生命值,每天开始训练时都必须重新设置当天的初始生命值。
需要的初始生命值越少,你就越熟练。请问总初始生命值
最少可以是多少?
输入格式
第一行包含两个整数 (,)。今天是第 0 天,因此总共训练 天。
接下来 行,每行包含四个整数 (),描述一只怪物。
输入只有一组数据。
输出格式
输出一行一个整数,表示最小总初始生命值对 取模的结果。以非负十进制整数输出。
样例
3 5
3 1 5 2
4 2 1 3
1 9 100 1
113
帮助理解的说明
样例中,第 0 至第 5 天各自需要的最少初始生命值依次为 ,总和为 。各天可以选择不同的战斗顺序,上一天的剩余生命值不带到下一天。