Background

This problem is translated from XXVIII Olimpiada Informatyczna – Stage I Cukiernia。

Problem Description

The Bajtuś bakery sells three kinds of food: cakes, donuts, and croissants. In the bakery, there are $n$ display shelves. Under normal conditions, each shelf should contain only one kind of food. But one morning, the bakery owner Bajtazara’s son Bajtuś sneaked into the bakery and messed up all the food placement.

The bakery is about to open. Bajtazara urgently wants to rearrange the food so that each shelf contains only one kind of food (in particular, it is also allowed for a shelf to be empty). Please help him find the minimum number of moves needed 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 contain three integers $d_i, p_i, r_i$, representing the current number of cakes, donuts, and croissants on the $i$-th shelf. The testdata guarantees that there is at least one piece of food in the bakery.

Output Format

Output one integer, the minimum number of moves required to move the food.

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

9

3
1 1 2
2 1 1
1 1 2

7

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

50

Hint

[Sample Explanation #1]:

One valid moving plan is as follows:

1. Move one donut from shelf $1$ to shelf $3$, and move one croissant from shelf $1$ to shelf $2$.
2. Move three donuts from shelf $2$ to shelf $3$.
3. Move one cake from shelf $3$ to shelf $1$, and move three croissants from shelf $3$ to shelf $2$.

After that, shelf $1$ contains only cakes, shelf $2$ contains only croissants, shelf $3$ contains only donuts, shelf $4$ contains only cakes, and shelf $5$ is empty.

[Constraints]:

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

Translated by ChatGPT 5