G. Primal Core Optimization: Attribute Balance
time limit per test
9 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are playing a game called "Rhythm Sin". In this game, you control partners to explore the "World".

Each partner has three attributes: $$$\mathrm{Stop}$$$ (S), $$$\mathrm{Flag}$$$ (F), and $$$\mathrm{Ever}$$$ (E). When all partners' attributes are completely consistent, they can successfully fuse.

Your goal is to fuse all partners, meaning you must make every pair of partners have identical attributes. To achieve this, you need to modify their attributes. Each modification consists of the following steps:

  1. Select any partner as the target (you can only select one partner).
  2. Choose any subset of her attributes.
  3. Increment or decrement all selected attributes by $$$1$$$ (the same operation must be carried out simultaneously, i.e., all selected attributes increment or all selected attributes decrement).

Due to limited magical power, each modification costs $$$1$$$ primal stone. Your task is to determine the minimum number of primal stones required to achieve your goal.

Input

The first line contains an integer $$$N$$$ ($$$1\le N\le 10^5$$$), the number of partners.

The next $$$N$$$ lines each contain three integers $$$S_i$$$, $$$F_i$$$, and $$$E_i$$$ ($$$1\le S_i, F_i, E_i \le 10^5$$$), separated by a space, representing the values of the three attributes for the $$$i$$$-th partner.

Output

A single integer representing the minimum number of primal stones required.

Examples
Input
3
2 2 2
2 2 2
1 2 3
Output
2
Input
3
2 3 1
3 5 3
3 2 1
Output
4
Input
1
201 502 10
Output
0
Input
4
1 2 3
1 2 3
4 5 6
4 5 6
Output
6
Note

For the first sample, one possible sequence of modifications (costing $$$2$$$ primal stones) is:

  1. Select partner $$$3$$$ and S attribute, modify her attributes to $$$2$$$, $$$2$$$, $$$3$$$;
  2. Select partner $$$3$$$ and E attribute, modify her attributes to $$$2$$$, $$$2$$$, $$$2$$$.

It can be proved that you cannot achieve the goal using less than $$$2$$$ primal stones, so the answer is $$$2$$$.

For the second sample, one possible sequence of modifications (costing $$$4$$$ primal stones) is:

  1. Select partner $$$1$$$ and S and E attributes, modify her attributes to $$$3$$$, $$$3$$$, $$$2$$$;
  2. Select partner $$$2$$$ and F and E attributes, modify her attributes to $$$3$$$, $$$4$$$, $$$2$$$;
  3. Select partner $$$2$$$ again and F attribute, modify her attributes to $$$3$$$, $$$3$$$, $$$2$$$;
  4. Select partner $$$3$$$ and F and E attributes, modify her attributes to $$$3$$$, $$$3$$$, $$$2$$$.

It can be proved that you cannot achieve the goal using less than $$$4$$$ primal stones, so the answer is $$$4$$$.

For the third sample, because there is only one partner, you don't need to perform any modifications, so the answer is $$$0$$$.