Noodle Team Contest
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:
step-1: Cook the noodle in a boiled water for 3 minutes, rain, and put into a dish.
step-2: Put the seasoning, stir, and done!
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:
1. Andoko. step-1 needs 2 minutes, step-2 needs 3 minutes.
2. Kurniady. step-1 needs 3 minutes, step-2 needs 4 minutes.
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.
Input
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.
Output
Sample Input
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
Output
8
51
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.