У Санта-Клауса есть Робот, который живёт на клетчатой плоскости и умеет перемещаться по линиям сетки. Если ему дать последовательность из m точек p₁, p₂, ..., p_m с целыми координатами, то он сделает следующее: обозначим точку, в которой он сейчас находится, через p₀. Тогда Робот сначала поедет по некоторому кратчайшему пути из p₀ в p₁ (обратите внимание, поскольку Робот ездит только по линиям сетки, кратчайших путей может быть несколько), затем, доехав до p₁, поедет к точке p₂, опять же, по какому-то кратчайшему пути, затем к точке p₃, и так далее, пока не пройдёт все точки в заданном порядке. Некоторые из точек в последовательности могут совпадать, тогда Санта-Клаус должен посетить их несколько раз в порядке, соответствующем последовательности.

Пока Санта-Клауса не было, кто-то дал Роботу несколько точек. Эта последовательность точек была утерян, но у вас есть протокол перемещений Робота (каждое перемещение на единицу длины). Узнайте, пожалуйста, минимальную возможную длину последовательности, заданной Роботу.