Minimizing Moves in Bajtazara's Bakery

Bajtazara's bakery sells three types of food: cakes, donuts, and croissants. There are (n) display shelves. Under normal conditions, each shelf should contain food items of only one type (an empty shelf is allowed). One morning, Bajtuś, the owner's son, secretly entered the bakery and mixed all the food up. As a result, for the (i)-th shelf, there are (a_i) cakes, (b_i) donuts, and (c_i) croissants.

To restore order before the store opens, Bajtazara needs to rearrange the food so that each shelf ends up containing items of at most one type. In each move, he can take a single food item from one shelf and move it to any other shelf. Note that items moved to a shelf must conform to that shelf's designated food type, or the shelf may be left empty.

The strategy is to choose for each shelf a food type so that the number of items already on that shelf that match that type is maximized. The cost for a shelf is the total number of food items on it minus the maximum count among the three types. Hence, the minimum number of moves required is given by: [ \text{Total Moves} = \sum_{i=1}^{n} \Bigl[(a_i+b_i+c_i) - \max(a_i, b_i, c_i)\Bigr]. ] Determine the minimum number of moves to achieve a configuration where every shelf holds food of at most one type.

inputFormat

The first line contains a single integer (n) ((1 \le n \le 10^5)) representing the number of shelves.

Each of the following (n) lines contains three non-negative integers (a_i), (b_i), and (c_i) (each not exceeding (10^9)), representing the number of cakes, donuts, and croissants on the (i)-th shelf, respectively.

outputFormat

Output a single integer representing the minimum number of moves required to rearrange the food such that every shelf holds items of at most one type.

sample

3
1 2 0
0 0 5
2 1 1

3