Balls in Boxes - Repovive Premier Round 2 | Repovive

3B. Balls in Boxes

1000 pts2s256 MB

You have $n$ boxes. In box $i$ there are $a_i$ red balls and $b_i$ blue balls.

In one operation, you choose one ball from some box and move it to a different box.

Your goal is to make every box monochromatic, meaning that it contains balls of at most one color (it may also become empty).

For each test case, find the minimum number of operations needed.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le a_i, b_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t \\[0.5em] \left. \begin{array}{l} n \\[0.25em] a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_n \quad b_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

2
10 10
3 7

Explanation

Case 1

Move 1 blue from box 1 to box 2, move 1 red from box 2 to box 1, and move 3 reds from box 3 to box 1.

Case 2

Move 1 blue from box 1 to box 2, move 2 reds from box 2 to box 3, move 2 blues from box 3 to box 2, and move 3 reds from box 4 to box 3.

Case 3

Move 10 blues from box 1 to box 2, and move 3 reds from box 2 to box 1.

Output

Case 1

Case 2

Case 3

You have $n$ boxes. In box $i$ there are $a_i$ red balls and $b_i$ blue balls.

In one operation, you choose one ball from some box and move it to a different box.

Your goal is to make every box monochromatic, meaning that it contains balls of at most one color (it may also become empty).

For each test case, find the minimum number of operations needed.

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$1 \le a_i, b_i \le 10^9$
The sum of $n$ over all test cases does not exceed $2 \times 10^5$

t \\[0.5em] \left. \begin{array}{l} n \\[0.25em] a_1 \quad b_1 \\ a_2 \quad b_2 \\ \vdots \\ a_n \quad b_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

3B. Balls in Boxes

Input

Output

Samples

3B. Balls in Boxes

Constraints

Input

Output

Samples

Constraints