|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||512 MB||5||2||2||40.000%|
There will be a noodle cooking contest! Each team consist of N (1 <= N <= 12) peoples. Each member of the team should cook his/her noodle, but the team will only have one pot/wok to cook the noodle. The first team to finish their noodles is the winner.
To cook a noodle, there are two steps:
Because there is only one pot, only one person in the team at a time can do step-1.
For example, there are two peoples in the team:
If Andoko be the first person to use the pot to do his step-1 (Kurniady wait for 2 minutes), then the team will need 9 minutes to finish their noodles. If Kurniady be the first person to use (Andoko wait for 3 minutes), then the team will need 8 minutes. Hence, letting Kurniady be the first person will lead to a better result (faster finish time).
Given the time for each member to complete his/her step-1 and step-2, find the minimum time needed by the team to finish all their noodles.
The first line of input contains an integer T (1 <= T <= 200000), the number of test cases follow.
Each test case starts with an integer N denoting the number of people in one team. The next N lines each contains 2 integers, T1 and T2 (0 <= T1 and T2 <= 1000) the time needed for each member to do step-1 and step-2 respectively.
For each test case, output in a line the the minimum time needed to finish all the noodles.
2 2 2 3 3 4 10 8 3 6 1 2 2 3 2 6 4 1 7 9 2 4 4 4 0 8 6