Survivor (Small)

You are shipwrecked on a deserted island. You saved one box of food, but the island is bare rock with no plants and you have no way to fish, so no more food arrives.

The box holds $N$ foods. For each food $i$ you know the remaining shelf life $P_i$, counted from now, and the time it holds off hunger $S_i$ once you eat it.

The rules for eating are these.

• You eat the first food right now, at minute 0.
• $P_i$ and $S_i$ are both measured in minutes.
• Food past its shelf life is thrown out at once. Food $i$ can only be eaten at a time of at most $P_i$ minutes, and a food whose remaining shelf life is 0 must be eaten right now or thrown out.
• You eat nothing while hunger is held off. If you eat food $i$ at minute $t$, the next food goes down at exactly minute $t + S_i$.
• If hunger arrives and no food is left to eat, you starve on the spot.

Choose which foods to eat and in what order, then report the longest time you survive on the island. If the last food is eaten at minute $t$ and its value is $S$, the survival time is $t + S$ minutes.

The first line holds the number of test cases $T$. Each test case follows in this format.

N
P1 S1
P2 S2
...
PN SN

Constraints

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

For each test case $x$, print one line in the form Case #x: y, where $y$ is the longest time you survive on the island in that test case.