chefmala

Chef and Mala

Chef is preparing a banquet of $N$ 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 $i$-th dish, Chef has assigned $4$ scores:

• $SA_i$ --- the spiciness felt by Sir Anton
• $NA_i$ --- the numbness felt by Sir Anton
• $ST_i$ --- the spiciness felt by Sir Trygub
• $NT_i$ --- 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 $\max\limits_{i \in A}(SA_i)+\max\limits_{i \in A}(NA_i)+\max\limits_{i \in T}(ST_i)+\max\limits_{i \in T}(NT_i)$ over all $(A,T)$, such that, $A \subseteq [1,N]$,$T \subseteq [1,N]$, $1 \leq |A|,|T|$ and $A \cup T = [1,N]$.

Input Format

• The first line of input contains one integer $T$ - the number of test cases.
• The first line of each test case contains one integer $N$ - the number of dishes.
• The next $N$ lines of each test case contain $4$ integers each denoting the values $SA_i, NA_i, ST_i$ and $NT_i$.

Output Format

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

Constraints

• $1 \leq T \leq 10^4$
• $1 \leq N \leq 2 \cdot 10^5$
• $0 \leq SA_i, NA_i, ST_i, NT_i \leq 10^9$
• It is guaranteed that the sum of $N$ over all test cases does not exceed $2 \cdot 10^5$

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 $A=\{1,2,3,4,5\}$ and $T=\{4\}$. This way, the disgust is $\max\limits_{i \in A}(SA_i)+\max\limits_{i \in A}(NA_i)+\max\limits_{i \in T}(ST_i)+\max\limits_{i \in T}(NT_i)=9+9+4+0=22$. It can be shown that this is the minimum disgust possible.
• In the second test case, $A = \{1\}$ and $T = \{2\}$. Thus, the disgust is $0+0+0+0 = 0$.