Safe Haven from Meteors

Bessie has heard that an extraordinary meteor shower is coming and is determined to find a safe haven—a location that is never hit by any meteors. She starts at the origin (0, 0) at time 0 in the first quadrant of the coordinate plane. There are M meteors (1 ≤ M ≤ 50,000). Each meteor i strikes point \((X_i, Y_i)\) (with \(0 \leq X_i, Y_i \leq 300\)) at time \(T_i\) (\(0 \leq T_i \leq 1000\)). When a meteor strikes, it destroys the target point as well as its four adjacent lattice points (up, down, left, and right).

Bessie can move along the axes (up, down, left, or right) at a rate of one unit per second. However, she cannot step into or remain on a point at any time \(t\) where \(t\) is greater than or equal to the time that point is destroyed. Bessie’s goal is to reach a safe location — one that is never destroyed by any meteor — in the shortest possible time. If she can’t reach such a location, output \(-1\).

Note: When Bessie moves to a point at time \(t\), it is only safe if \(t\) is strictly less than its destruction time.

inputFormat

The first line contains an integer M, the number of meteor strikes.

Each of the following M lines contains three integers \(X_i\), \(Y_i\) and \(T_i\) representing the coordinates of the meteor strike and the time at which it strikes.

\(1 \leq M \leq 50,000, 0 \leq X_i, Y_i \leq 300, 0 \leq T_i \leq 1000\).

outputFormat

Output a single integer: the minimum time Bessie needs to reach a safe place. If it is impossible for her to reach any safe place, output \(-1\).

sample

2
1 1 2
0 1 2

2