Borscht, potatoes and salad

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Today is a holiday for the Plast members! Twice as much food was brought for lunch. Zenyk and Marichka volunteered to help in the kitchen. There are three different dishes in total: borscht, potatoes, and salad.

Zenyk and Marichka have \(n\) friends in Plast. The \(i\)-th friend wants to eat \(a_i\) grams of borscht, \(b_i\) grams of potatoes, and \(c_i\) grams of salad. If Zenyk and Marichka’s friend wants to eat \(x\) grams of a certain dish, but is served \(y\) grams on their plate, then this friend’s distrust level towards Zenyk and Marichka will increase by \(|x-y|\) units. Zenyk and Marichka were instructed to serve everyone equal portions of a certain dish. That is, each friend needs to be served \(A\) grams of borscht, \(B\) grams of potatoes, and \(C\) grams of salad.

Help Zenyk and Marichka choose such \(A\), \(B\), and \(C\) that the total distrust level of all friends is as small as possible.

Input

The first line contains a single integer \(n\) — the number of friends of Zenyk and Marichka.

The next \(n\) lines contain three integers \(a_i\), \(b_i\), \(c_i\) each — the amount of borscht, potatoes, and salad that the \(i\)-th friend wants to receive.

Output

In a single line, print one integer — the total distrust level of all friends towards Zenyk and Marichka.

Constraints

\(2 \le n \le 10^5\), \(n\) is even.

30% of tests:

\(0 \le a_i, b_i, c_i \le 444\).

70% of tests:

\(0 \le a_i, b_i, c_i \le 10^4\).

Samples

Input (stdin) сopy	Output (stdout) сopy
2 10 50 100 70 10 50	150

Notes

One of the optimal choices of numbers \(A\), \(B\), \(C\) for Zenyk and Marichka is \(A=40\), \(B=30\), \(C=75\).

Then the distrust level of the friends will be as follows:

• Friend 1: \({|40-10| + |30-50| + |75-100| = 30 + 20 + 25 = 75}\)

• Friend 2: \({|40-70| + |30-10| + |75-50| = 30 + 20 + 25 = 75}\)

Total distrust level — \({75 + 75 = 150}\).