#P7989. Pty plays game

Pty plays game

题目描述

Pty 和怪物分别率领一队士兵。挑战开始时,两队的第一名士兵交战。两名正在交战的士兵持续对彼此造成伤害。士兵的生命值变为 00 时,由本队下一名士兵接替他。交战时间可以是非整数。只有当某队仍有士兵存活、另一队全灭时,前者才获胜。

两队持续训练。每名士兵都有自己的初始生命值和初始每秒伤害,这两个量每天分别增加固定的数值。挑战在同一天内完成,两队都必须按给定的顺序派出士兵。

求 Pty 能获胜的最小等待天数 xx。如果现在就能获胜,答案为 00。如果在 101810^{18} 天内不能获胜,则输出 none。

输入格式

第一行是测试组数 TT。

每组第一行是 n,mn,m,分别表示 Pty 和怪物的士兵人数。接下来 nn 行依次描述 Pty 的士兵,随后 mm 行描述怪物的士兵。每名士兵用四个整数描述,依次为初始生命值、每日生命值增量、初始每秒伤害、每日每秒伤害增量。

输出格式

每组输出一行最小等待天数,或输出 none。

数据范围

1≤n,m≤1051\le n,m\le10^5,所有测试组的 n+mn+m 之和不超过 2×1062\times10^6。初始生命值和每秒伤害均在 [0,106][0,10^6] 内,两种每日增量均在 [0,103][0,10^3] 内。

样例

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

原 PDF 题面