Problem Description

Bajtuś Bakery sells three types of food: cakes, doughnuts, and croissants. In the bakery, there are $n$ shelves, and under normal circumstances, each shelf should only hold one type of food. However, one morning, Bajtazara's son Bajtuś sneaked into the bakery and mixed up all the food.

The bakery is about to open, and Bajtazara urgently wants to rearrange the food so that each shelf holds only one type of food (it is also allowed for a shelf to be empty). Please help him determine the minimum number of moves required to achieve this goal.

Input Format

The first line contains an integer $n$, representing the number of shelves in the bakery.

The next $n$ lines, each containing three integers $d_i, p_i, r_i$, represent the number of cakes, doughnuts, and croissants on the $i$-th shelf, respectively. The data guarantees that there is at least one food item in the bakery.

Output Format

Output a single integer, which is the minimum number of moves required to rearrange the food.

Sample Input and Output

Sample Input #1

5
5 1 1
0 3 4
1 4 3
4 0 0
0 0 0

Sample Output #1

9

Sample Input #2

3
1 1 2
2 1 1
1 1 2

Sample Output #2

7

Sample Input #3

5
5 5 5
5 5 5
5 5 5
5 5 5
5 5 5

Sample Output #3

50

Notes

Sample Explanation #1:

One valid moving scheme is as follows:

1. Move one doughnut from shelf $1$ to shelf $3$, and one croissant from shelf $1$ to shelf $2$;
2. Move three doughnuts from shelf $2$ to shelf $3$;
3. Move one cake from shelf $3$ to shelf $1$, and three croissants from shelf $3$ to shelf $2$;

After these moves, shelf $1$ has only cakes, shelf $2$ has only croissants, shelf $3$ has only doughnuts, shelf $4$ has only cakes, and shelf $5$ is empty.

Data Range:

All test cases satisfy: $3 \leq n \leq 3 \times 10^5$, $0 \leq d_i, p_i, r_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分