小奇装箱

小奇装箱

问题描述

小奇买了一些蛋糕,由两条流水线运输。它站在中间,两条流水线分别将蛋糕投放到两个箱子中。箱子的初始容量是一单位蛋糕。
在每一个时刻,小奇左右两边各有\(a_i\),\(b_i\);个单位蛋糕从流水线投到箱子里,蛋糕投放到箱子之后,小奇可以选择从其中一个箱子里拿一单位蛋糕吃掉,暂时没法拿走的蛋糕只能先存在箱子里。
小奇不想浪费,它想知道它至少要把箱子扩大几个单位容量,才能没有蛋糕溢出。

输入格式

第一行输入一个T,表示有T组数据
每组数据第一行输入一个n,表示蛋糕投放持续n个时刻。

输出格式

输出文件名为box.out
输出\(T\)行,对于每组数据,输出需要扩大的容量。

样例输入

3
1
11
3
32
03
20
6
01
1 1
12
1 1
1 1
6 0

样例输出

0  3  5

数据规模与约定

对于30%的数据,有 \(T≤10,n≤30\) 。 对于100%的数据,有 \( T≤100,n≤10000,0≤a_1,b_1≤20 \)

信息

ID
1391
难度
9
分类
其他 | 二分查找 点击显示
标签
(无)
递交数
3
已通过
1
通过率
33%
上传者