火车

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

线性王国只有一条铁路,它有n个车站,按照火车前进的方向编号1到n。在第i个车站会有Ai个乘客下车,同时会有Bi个乘客上车。火车在到达第一个车站前是空的,同样在到达最后一个车站后,车上所有的乘客都会下车,火车也会变成空的。
你的任务是计算火车的最小容量确保任何时候火车上的总人数都不会超过这个容量。注意,在每个车站,上车的乘客都是在下车乘客都下来之后才开始上的。

Input

多组输入,第一行是一个正整数T,代表组数。
每组输入数据第一行只有一个整数n (2 <= n <= 1000) ——车站的总数。
接下来是n行,每行有两个整数Ai和Bi(0 <= Ai,Bi <= 1000)——分别代表在第i个车站下车和上车的乘客数。车站是沿照火车前进方向从起点到终点按顺序给出的。
注意起点站不会有人下车,终点站不会有人上车。

Output

每组输出只有一个整数代表火车的最小容量(可以是0)。每组输出之后输出一个空行。

Sample Input

1
4
0 3
2 5
4 2
4 0

Sample Output

6

Hint

Source