Lucky Cookie Bakery

Dev Bakery gives lucky cookies to its staff for an anniversary. Cheolsu, who takes care of the snacks, got the job of baking them.

Cheolsu has to bake all $N$ balls of lucky dough with two ovens. Each ball is baked in exactly one of the two ovens, and the baking time depends on which oven it goes into. The two ovens run at the same time and are independent of each other, but one oven bakes only one ball at a time. An oven therefore finishes at the sum of the baking times of the balls assigned to it, and the whole job finishes when the later of the two ovens finishes. Putting a ball in or taking it out takes no time.

Cheolsu goes home only after every ball is baked. Find the minimum time needed to bake all of them.

The first line has the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case has the number of dough balls $N$ ($1 \le N \le 1000$). Each of the next $N$ lines has the time $a_i$ to bake one ball in oven 1 and the time $b_i$ to bake the same ball in oven 2, separated by one space ($1 \le a_i, b_i \le 100$).

For each test case, print the minimum time needed to bake every dough ball on its own line.