Степан збирається бігти марафон. Дистанція включає ~N~ контрольних пунктів, які треба відвідати почергово від 1 до  ~N~. Він зараз не в формі і хоче пропустити один контрольний пункт (не 1 і не  ~N~, звичайно).

Допоможіть Степану знайти мінімальну відстань, яку йому треба пробігти, якщо він пропустить один контрольний пункт.

Примітка. Відстань між двома точками (~x_1,y_1~) та (~x_2,y_2~) манхетенська: ~|x_1-x_2| + |y_1-y_2|~, оскільки рухатися можна лише паралельно осям координат.

Input

Перший рядок вхідного файлу містить ціле число ~N~ (~1 \le N \le 10^5~)

Наступні ~N~ рядків містять цілі числа ~x_i, y_i~ (~-1000 \le x_i,y_i \le 1000~).

Контрольні пункти задаються у тому порядку, в якому їх треба відвідати. Маршрут може мати самоперетини і декілька контрольних пунктів можуть міститися в одній позиції. Коли Степан пропускає контрольну точку, то він пропускає її, а не всі контрольні точки у цій позиції.

Числа у рядках розділяються пропуском.

Output

У вихідний файл вивести шукану мінімальну відстань.

Sample Input 1

4
0 0
8 3
11 -1
10 0

Sample Output 1

14

Notes

Слід пропустити точку (8,3) і отримаємо мінімальну відстань 14.