There are sheep, labelled from to , 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 -th sheep has a position of and has a degree field of view. Their field of view is denoted by an integer, , representing one of the following four fields of view:

- If , then the -th sheep can see the -th sheep if and only if and .
- If , then the -th sheep can see the -th sheep if and only if and .
- If , then the -th sheep can see the -th sheep if and only if and .
- If , then the -th sheep can see the -th sheep if and only if and .

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

- Move unit in any of the four cardinal directions. That is, decrease by , increase by , decrease by , or increase by .
- Rotate their field of view by degrees. That is, change the field of view from to mod or mod .

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

##### Subtask 1 [60%]

##### Subtask 2 [40%]

No additional constraints.

#### Input Specification

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

The -th of the following lines of input contains three space-separated integers, , representing the initial position and field of view of the -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 -st sheep to move to , and for the -rd sheep to rotate their field of view twice such that .

## Comments