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

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

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.

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