There are ~N~ sheep, labelled from ~1~ to ~N~, who are in a field. Wary of coyotes, the sheep vow to protect each other by positioning themselves such that every sheep can see every other sheep.

The ~i~-th sheep has a position of ~(X_i, Y_i)~ and has a ~90~ degree field of view. Their field of view is denoted by an integer, ~V_i~, representing one of the following four fields of view:

• If ~V_i = 0~, then the ~i~-th sheep can see the ~j~-th sheep if and only if ~X_i \le X_j~ and ~Y_i \le Y_j~.
• If ~V_i = 1~, then the ~i~-th sheep can see the ~j~-th sheep if and only if ~X_i \le X_j~ and ~Y_i \ge Y_j~.
• If ~V_i = 2~, then the ~i~-th sheep can see the ~j~-th sheep if and only if ~X_i \ge X_j~ and ~Y_i \ge Y_j~.
• If ~V_i = 3~, then the ~i~-th sheep can see the ~j~-th sheep if and only if ~X_i \ge X_j~ and ~Y_i \le Y_j~.

Sheep can perform moves to reposition or reorient themselves. In one move, the ~i~-th sheep can perform one of the following actions:

• Move ~1~ unit in any of the four cardinal directions. That is, decrease ~X_i~ by ~1~, increase ~X_i~ by ~1~, decrease ~Y_i~ by ~1~, or increase ~Y_i~ by ~1~.
• Rotate their field of view by ~90~ degrees. That is, change the field of view from ~V_i~ to ~(V_i+1) \bmod 4~ or ~(V_i-1) \bmod 4~.

What is the minimal total number of moves performed by the sheep such that every sheep can see every other sheep? Note that multiple sheep are allowed to have the same position.

Constraints

~2 \le N \le 10^6~

~-10^9 \le X_i, Y_i \le 10^9~

~0 \le V_i \le 3~

Subtask 1 [60%]

~2 \le N \le 2\,000~

Subtask 2 [40%]

No additional constraints.

Input Specification

The first line of input contains a single integer ~N~, representing the number of sheep.

The ~i~-th of the following ~N~ lines of input contains three space-separated integers, ~X_i, Y_i, V_i~, representing the initial position and field of view of the ~i~-th sheep.

Output Specification

On a single line, output the minimal total number of moves performed by the sheep such that every sheep can see every other sheep.

Sample Input

3
1 2 1
2 1 0
4 2 0

Sample Output

3

Explanation

It is optimal for the ~1~-st sheep to move to ~(2, 2)~, and for the ~3~-rd sheep to rotate their field of view twice such that ~V_3 = 2~.