Problem B: Game

Problem B: Game

Time Limit: 2 Sec  Memory Limit: 512 MB
Submit: 427  Solved: 120
[Submit][Status][Web Board]

Description

Alice must go to school everyday, but she wants to make the journey interesting, so she would like to play a game this time.

There are n stones on the road,  Alice go though these stones step by step. In each step, Alice could go to the next nearest stone. She will throw this stone ahead if the current number of step is odd, otherwise, she will skip it.  Now, you have the information about the stones, i.e., each stone has two attributes: Pi  (the position of that stone) and Di (the throw distance of that stone), and you are asked to find the largest distance Alice could walk. 

Please note that if there are two or more stones at the same position, Alice will go to the one with the smallest Di first.

Input

The first line will be an integer T, which is the number of test cases. (1 <= T <= 3). For each test case, the first line will be an integer n(1 <= n <= 105), then followed by n lines, each line will be two integers Pi(1 <= Pi <= 109) and Di(1 <= Di <= 109), Pi means the position of the i-th stone, Di means how far Alice can throw it.

Output

Output one line for each test, the largest distance Alice could walk.

Sample Input

1
2
1 1
2 2

Sample Output

4

HINT

If there is a stone, its position is Pi and its throw distance is Di,  and you can throw it, it can only be threw to the position Pi  + Di  

[Submit][Status]