Crop Harvest

Dadas is farming on a number line. Initially, there are $N$ planted seeds. Seed $i$ is located at coordinate $x_i$, and all seed positions are distinct.

Seed $i$ has value $w_i$. It can be harvested only on day $i$.

Dadas may choose any initial position on the number line. Dadas may also choose not to harvest a seed on a day. To harvest seed $i$ on day $i$, Dadas must move from the current position to $x_i$.

If there is an unharvested seed strictly between the current position and $x_i$, Dadas steps on it while moving. A stepped-on seed can never be harvested later. The target seed $i$ itself is not considered stepped on.

Choose which seeds to harvest to maximize the total value obtained.

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

Each case is given in the following format:

$N$ $x_1\ w_1$ $x_2\ w_2$ $\vdots$ $x_N\ w_N$

For each test case, print the maximum total value that can be obtained on one line.

• $1 \leq T \leq 100$.
• $1 \leq N \leq 200\,000$.
• $1 \leq x_i \leq 10^9$ ($1 \leq i \leq N$).
• $x_i \neq x_j$ ($1 \leq i < j \leq N$).
• $1 \leq w_i \leq 10^9$ ($1 \leq i \leq N$).
• The sum of $N$ over all test cases does not exceed $200\,000$.