chefmala

Chef and Mala


Chef is preparing a banquet of dishes for Sir Anton and Sir Trygub. Unfortuantely, Sir Anton and Sir Trygub only told the Chef three days before the banquet that they do not like food that is too spicy or too numb.

For the -th dish, Chef has assigned scores:

  • --- the spiciness felt by Sir Anton
  • --- the numbness felt by Sir Anton
  • --- the spiciness felt by Sir Trygub
  • --- the numbness felt by Sir Trygub

Chef will serve some dishes to Sir Anton and Sir Trygub. A serve is said to be good, if both of the following conditions are satisfied:

  • All dishes are served to at least one of the Sirs.
  • Both Sirs are served at least one dish.

The total disgust of a good serve is defined as the sum of the maximum spiciness felt by Sir Anton, the maximum numbness felt by Sir Anton, the maximum spiciness felt by Sir Trygub and the maximum numbness felt by Sir Trygub.

Find the minimum disgust possible amongst all the good serves.

More formally, find the minimum value of over all , such that, ,, and .


Input Format

  • The first line of input contains one integer - the number of test cases.
  • The first line of each test case contains one integer - the number of dishes.
  • The next lines of each test case contain integers each denoting the values and .

Output Format

For each test case, print in a single line, the minimum disgust possible amongst all the good serves.


Constraints

  • It is guaranteed that the sum of over all test cases does not exceed

Sample Input 1

2
5
1 7 1 9
7 8 9 8
9 1 10 10
6 9 4 0
5 9 5 5
2
0 0 1 2
3 4 0 0

Sample Output 1

22
0

Explanation

  • In the first test case, a possible solution is to let and . This way, the disgust is . It can be shown that this is the minimum disgust possible.
  • In the second test case, and . Thus, the disgust is .

 


Submitting .cpp to 'chefmala'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2 Seconds
Memory Limit: 1024MB
No. of ACs: 1
Your best score: 0
Source: CodeChef February Lunchtime 2022 (errorgorn)
Editorial: 1

Subtask Score
1 100