В прямоугольном болоте живут 10 видов лягушек. i-й вид лягушек умеет совершать прыжки на длину ровно i параллельно любой из осей координат в любом направлении. Изначально лягушки всех видов собрались на кочке с координатами (0, 0). Вам даны координаты N кочек на болоте (за исключением исходной кочки). Найдите максимальное манхэттенское расстояние, на которое может отдалиться какая-нибудь из лягушек от начала координат, прыгая с кочки на кочку.
Манхэттенское расстояние между точками (x1, y1) и (x2, y2) опеределяется как |x1 - x2| + |y1 - y2|.
Выходные данные
Выведите целое число — максимальное манхэттенское расстояние, на которое какая-то из лягушек может упрыгать от начала координат.
Примечание
В первом примере лягушки видов 1, 2 и 3 могут прыгнуть на первую, вторую и третью кочки, соответственно.
Во втором примере лягушка вида 2 может прыгнуть на вторую кочку, с нее на четвертую и затем на пятую.
В третьем примере ни одна лягушка не может допрыгнуть до кочки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 1
0 -2
0 3
|
3
|
|
2
|
5
0 1
0 2
0 3
2 2
2 4
|
6
|
|
3
|
1
18 0
|
0
|