У Санта-Клауса есть Робот, который живёт на клетчатой плоскости и умеет перемещаться по линиям сетки. Если ему дать последовательность из m точек p1, p2, ..., pm с целыми координатами, то он сделает следующее: обозначим точку, в которой он сейчас находится, через p0. Тогда Робот сначала поедет по некоторому кратчайшему пути из p0 в p1 (обратите внимание, поскольку Робот ездит только по линиям сетки, кратчайших путей может быть несколько), затем, доехав до p1, поедет к точке p2, опять же, по какому-то кратчайшему пути, затем к точке p3, и так далее, пока не пройдёт все точки в заданном порядке. Некоторые из точек в последовательности могут совпадать, тогда Санта-Клаус должен посетить их несколько раз в порядке, соответствующем последовательности.
Пока Санта-Клауса не было, кто-то дал Роботу несколько точек. Эта последовательность точек была утерян, но у вас есть протокол перемещений Робота (каждое перемещение на единицу длины). Узнайте, пожалуйста, минимальную возможную длину последовательности, заданной Роботу.
Примечание
Ниже приведены иллюстрации к первым трём тестам.
Последний пример показывает, что каждая точка в последовательности должна быть посчитана столько раз, сколько она в ней встречается.