#P7989. Pty plays game
Pty plays game
题目描述
Pty 和怪物分别率领一队士兵。挑战开始时,两队的第一名士兵交战。两名正在交战的士兵持续对彼此造成伤害。士兵的生命值变为 时,由本队下一名士兵接替他。交战时间可以是非整数。只有当某队仍有士兵存活、另一队全灭时,前者才获胜。
两队持续训练。每名士兵都有自己的初始生命值和初始每秒伤害,这两个量每天分别增加固定的数值。挑战在同一天内完成,两队都必须按给定的顺序派出士兵。
求 Pty 能获胜的最小等待天数 。如果现在就能获胜,答案为 。如果在 天内不能获胜,则输出 none。
输入格式
第一行是测试组数 。
每组第一行是 ,分别表示 Pty 和怪物的士兵人数。接下来 行依次描述 Pty 的士兵,随后 行描述怪物的士兵。每名士兵用四个整数描述,依次为初始生命值、每日生命值增量、初始每秒伤害、每日每秒伤害增量。
输出格式
每组输出一行最小等待天数,或输出 none。
数据范围
,所有测试组的 之和不超过 。初始生命值和每秒伤害均在 内,两种每日增量均在 内。
样例
2
3 2
2 3 1 3
3 2 4 3
1 2 2 3
3 3 4 2
4 1 1 3
1 1
1 1 1 1
1 1 1 1
1
none