Description

You may think that frogs are only good for leaping and croaking, but it turns out that they are also quite proficient coders! Your task is to choose three frogs which would form the best team for OpenFrogCup.

In the frogs’ favourite pond there are $n$ stones in a row, spaced 1 meter apart from each other. On every stone, a frog sits. Stones (and frogs) are numbered $1, 2, \ldots, n$ from the leftmost to the rightmost one. The $i$-th frog sits on $i$-th stone and is described by two parameters: its leap range $r_i$ and its programming skill $s_i$. The frog can reach any stone which is not farther than $r_i$ meters (in other words, any stone with index $j$ in $[i - r_i, i + r_i]$). Each frog is willing to jump at most once.

The team for OpenFrogCup must consist of exactly three members which can train together. This means that there must be a stone that all three frogs can jump to (allowing zero-length jumps). Determine the largest possible sum of programming skills of such a team.

The limits for the problem guarantee that there always exists at least one possible three-frog team.

Input Format

The first line of input contains the number of test cases $z$ ($1 \leq z \leq 30$). The test cases follow, each one in the following format:

The first line of a test case contains an integer $n$ ($3 \leq n \leq 200\,000$) – the number of stones (and also the frogs). Each of the following $n$ lines contain two integers $r_i, s_i$ ($1 \leq r_i, s_i \leq 200\,000$) – the range and the skill of the $i$-th frog, respectively.

The sum of $n$ values over all test cases does not exceed $500\,000$.

Output Format

For every test case, output a single integer – the largest possible sum of skills of a three-frog team.

3
4
1 39
2 17
4 5
1 40
3
1 10
1 20
1 30
7
5 4
4 3
3 2
2 1
3 2
4 3
5 4

62
60
11