[JSOI2010]蔬菜庆典

时间限制:10s      空间限制:64MB

题目描述


输入格式


输出格式

对于每组数据,输出一行。若蔬菜的总价能无限制增大,输出"+inf"(不含引号)。否则输出一个整数,表示所有蔬菜的最大总价。


样例输入

5
-1 3
1 2
1 1
3 2
3 2
5
-1 3
1 2
1 1
3 2
3 3
0


样例输出

13
+inf


提示

数据规模 对 的测试点,保证所有数据都是链,且每个测试点中 的总和不超过 对 的测试点,保证所有数据都是链 提示 若直接用递归DFS整个蔬菜结构,则可能栈溢出。


题目来源

没有写明来源