Bessie слышит о необычайном метеорном дожде: по сообщениям, метеоры столкнутся с землёй и уничтожат всё, во что попадут. Беспокоясь о безопасности, она решает найти путь в безопасное место, никогда не уничтожаемое метеором. Сейчас она пасётся в начале координат и хочет перейти в более безопасное место, избегая уничтожения по дороге.

Упадут $M$ метеоров, $(1 \le M \le 50,000)$. Метеор $i$ попадёт в $(X_{i}, Y_{i})$, $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$, в момент $T_{i}$, $(0 \le T_{i} \le 1,000)$. Он уничтожает точку попадания и четыре соседние по горизонтали или вертикали точки решётки.

Bessie выходит из начала координат в момент $0$ и движется в первом квадранте параллельно осям со скоростью единица расстояния в секунду к любой ещё не уничтоженной соседней точке (обычно их четыре). Она не может находиться в точке в момент её уничтожения или позже.

Найдите минимальное время достижения безопасного места.

Входные данные

Читайте данные из стандартного ввода.

• Строка $1$: одно целое $M$.

• Строки $2,\ldots,M+1$: строка $i+1$ содержит три целых через пробел: $X_{i}$, $Y_{i}$, $T_{i}$.

Выходные данные

Пишите результат в стандартный вывод.

• Строка $1$: минимальное время или $-1$, если это невозможно.

Примеры

Входные данные 1

4
0 0 2
2 1 2
1 1 2
0 3 5

Выходные данные 1

5

Примечание

Четыре метеора попадают в $(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$ соответственно в моменты $2$, $2$, $2$, $5$.

    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = падение метеора
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = уничтоженное пастбище
1|. . . . . . .     1|# * * # . . .     1|# # # # . . .   
0|B . . . . . .     0|* # # . . . .     0|# # # . . . .   
  --------------      --------------      -------------- 
  0 1 2 3 4 5 6       0 1 2 3 4 5 6       0 1 2 3 4 5 6

На рисунке при $t=5$ ближайшая безопасная точка — $(3, 0)$, но второй метеор слишком рано преграждает путь к ней. Следующая, $(4,0)$, тоже перекрывается слишком рано. Далее идут точки диагонали $(0,5)$-$(5,0)$. Из них $(0,5)$, $(1,4)$, $(2,3)$ достижимы за $5$ единиц времени.

       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    положения Bessie во времени
       2|2 . . . . . .    для одного решения
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6

Автор задачи: Jeffrey Wang, 2007