Survivor (Large)

You are stranded on a deserted island. You managed to grab one box of food, but the island is bare rock with no plants and no way to fish, so no more food is coming.

The box holds $N$ foods. Each food $i$ is labeled with its remaining shelf life $P_i$ and the satiation time $S_i$ it keeps hunger away once you eat it. Both values are measured in minutes.

The rules for eating are the following.

• You start eating now, at minute 0.
• Food past its shelf life is discarded at once. At minute $t$ you may eat only a food with $P_i \ge t$. A food whose remaining shelf life is 0 must be eaten right now or thrown away.
• If you eat food $i$ at minute $t$, you eat nothing else until minute $t + S_i$.
• The moment minute $t + S_i$ arrives, you starve to death immediately unless you eat another food.

Find the longest time you can survive on the island.

The first line contains the number of test cases $T$. Each test case has the following form.

The first line contains the number of foods $N$. Each of the next $N$ lines contains the remaining shelf life $P_i$ and the satiation time $S_i$ of one food, separated by a space.

Constraints

• Every input value is an integer.
• $1 \le T \le 100$
• $1 \le N \le 1000$
• $0 \le P_i \le 100000$
• $1 \le S_i \le 1000$

For each test case $x$, print the longest survival time $y$ on one line in the form Case #x: y.