SHOOOOM! Your team is captured, knocked unconscious (again), and tossed into a futuristic cell aboard the alien ship. Fortunately, as computer science students from South Australia, breaking computer systems comes naturally to you.

You make your way to the power room, where you find a collection of batteries. Each battery has:

• An integer type, ~T_i~.
• An integer positive potential, ~P_i~.
• An integer negative potential, ~N_i~.
• Each battery has a unique combination of positive and negative potentials.

You discover that connecting two batteries of the same type causes an explosion. When connecting two batteries ~A~ and ~B~ of the same type, the power of their explosion is calculated by the formula:

~\text{power} = \text{abs}(P_A - P_B) + \text{abs}(N_A - N_B)~

To avoid alerting the aliens, you want to cause the lowest-power explosion possible. But you must still escape, so you need to cause an explosion. What is the lowest-power explosion you can make?

Input

The first line consists of a single integer, ~n~ ~(1 \leq n \leq 4 \times 10^4)~, the number of batteries in the power room.

The next ~n~ lines contain ~T~, ~P~ and ~N~, indicating that there is a battery of type ~T~ ~(1 \leq T \leq 4 \times 10^4)~ with positive potential ~P~ and negative potential ~N~ ~(1 \leq P, N \leq 200)~.

Output

Output the minimum power of an explosion caused by combining two batteries of the same type. If it is impossible to cause any explosion, output ~-1~.

Example

Input 1

7
1 1 5
1 5 5
2 3 9
2 8 3
2 9 9
2 9 1
4 1 1

Output 1

3

There are many ways to choose ~2~ batteries of the same type. If you choose the fourth (2 8 3) and sixth (2 9 1) battery in the list, then the resultant explosion will have a power of:

~\text{power} = \text{abs}(P_A - P_B) + \text{abs}(N_A - N_B) = \text{abs}(8 - 9) + \text{abs}(3 - 1) = 1 + 2 = 3~

It can be shown that no other combination of batteries will cause an explosion with lesser power.

Input 2

4
1 1 1
1 2 6
2 9 8
3 7 6

Output 2

6

There is only one pair combination of batteries you can choose with the same type. Combining them causes an explosion with a power of ~3~.

Input 3

3
1 1 1
2 2 2
3 3 3

Output 3

-1

No two batteries have the same type, so it is impossible to make an explosion.