The "Bajtuś" bakery specializes in baking sweet buns, donuts, and croissants. There are $n$ display cases in the bakery. Each display case should contain only one type of pastry. However, one morning, Bajtuś—the son of the bakery owner, Bajtazar—snuck into the bakery and rearranged the pastries between the display cases while his father was away.

The bakery is about to open! Bajtazar wants to rearrange the pastries so that each display case again contains only one type of pastry. Help him and write a program that calculates the minimum number of pastry moves required to achieve this.

Input

The first line of the input contains a single integer $n$, representing the number of display cases.

The next $n$ lines describe the display cases: the $i$-th line, for $i = 1, \dots, n$, contains three integers $d_i, p_i,$ and $r_i$ ($0 \le d_i, p_i, r_i \le 10^9$), representing the number of sweet buns, donuts, and croissants, respectively, currently in the $i$-th display case. You may assume that there is at least one pastry in the bakery.

Output

The first and only line of the output should contain a single integer representing the minimum number of pastry moves between display cases necessary for each display case to contain exactly one type of pastry. If a display case ends up with no pastries at all, this condition is also satisfied.

Examples

Input 1

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

Output 1

9

Note

An optimal way to rearrange the pastries could look as follows: 1. Move a donut from display case 1 to display case 3 and a croissant from display case 1 to display case 2. 2. Move three donuts from display case 2 to display case 3. 3. Move a sweet bun from display case 3 to display case 1 and three croissants from display case 3 to display case 2.

In this way, 9 moves will be performed, after which the contents of the display cases will be as follows: display case 1: sweet buns, display case 2: croissants, display case 3: donuts, display case 4: sweet buns, and display case 5 will be empty.

Subtasks