408573: GYM103192 D 法力风暴
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
D. 法力风暴time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output
zyw最近迷上了一款TCG(Trading Card Game)桌游,万智牌。 在万智牌中有着5种不同的基础法术力。 玩家可以使用不同的法术力可以释放不同的咒语来进行史诗级的对决。
为了简化题目,我们假定只有红色与蓝色的法术力。
在游戏的某个回合中,zyw拥有着n张可以释放的咒语,每个咒语都有其法术力的消耗,第i个咒语的消耗是ri个红色法术力和bi个蓝色法术力。
zyw突然发现自己竟一个法术都无法释放,他十分无奈只能跳过这一回合。
请问zyw这回合最多可能拥有多少点法术力(红色和蓝色的总和)。
Input第一行给出一个整数T,表示题目一共有T组数据。
对于每组数据,第一行给出一个整数n(n ≤ 5000)。
第2到n + 1行每行给出两个整数,第i + 1行的两个整数表示ri与bi(ri ≤ 106, bi ≤ 106)。
保证对于任意的i,有ri + bi > 0。
保证Σ{n} ≤ 5000
Output对于每组数据,输出一个整数,表示zyw最多可能拥有的法术力点数,如果是无限点,则输出INF三个大写字母。
ExampleInput2 3 0 3 3 0 2 2 3 1 3 2 2 3 1Output
3 INF