Noodle Team Contest
InterviewTime limit2sMemory limit512 MB
Given each member's pot time and seasoning time, order the members to minimize the total time until all noodles are finished.
- Level
Medium6 of 10
- Topics
- Greedy, Sorting, Dynamic programming
- Solved
- No attempts yet
Problem
There will be a noodle cooking contest! Each team consists of N (1 <= N <= 12) people. 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 boiled water for 3 minutes, drain, 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 people in the team:
- Andoko. step-1 needs 2 minutes, step-2 needs 3 minutes.
- Kurniady. step-1 needs 3 minutes, step-2 needs 4 minutes.
If Andoko is the first person to use the pot to do his step-1 (Kurniady waits for 2 minutes), then the team will need 9 minutes to finish their noodles. If Kurniady is the first person to use it (Andoko waits 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
The first line of input contains an integer T (1 <= T <= 200000), the number of test cases that follow.
Each test case starts with an integer N denoting the number of people in one team. The next N lines each contain 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
For each test case, output in a line the minimum time needed to finish all the noodles.