Анни устала выигрывать все контесты и получать бесконечный рейтинг, поэтому сегодня вместо контеста она поехала сажать картошку.
Участок Анни можно представить в виде бесконечной плоскости. Анни должна посадить \(n\) кустов картошки, \(i\)-й куст должен быть посажен в точке \((x_i,y_i)\). Анни начнет в точке \((0, 0)\), и за один шаг будет перемещаться на одну единицу длины вправо или вверх (т. е. увеличивать свою координату \(x\) или \(y\) на \(1\)). Из любой точки \((X,Y)\) в процессе движения она может посадить любое количество кустов в любых точках плоскости, используя свою картофельную пушку. Для посадки одного куста в точку \((x,y)\) требуется \(\max(|X-x|,|Y-y|)\) единиц энергии. Найдите минимальное количество энергии, необходимое для посадки всех кустов картошки.
Обратите внимание, что Анни может посадить любое количество кустов из любой точки.
Выходные данные
Выведите минимальное количество энергии, необходимое для посадки всей картошки.
Примечание
В примере \(1\) Анни может посетить все необходимые точки, поэтому энергия не требуется.
В примере \(2\) Анни сначала может пойти в \((1,0)\), посадить оттуда второй куст, используя \(1\) единицу энергии. Затем она пойдет в \((1,1)\) и посадит первый куст, используя \(0\) единиц энергии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 1
2 2
|
0
|
|
2
|
2
1 1
2 0
|
1
|
|
3
|
3
5 5
7 7
4 9
|
2
|
|
4
|
10
5 1
4 0
9 6
0 2
10 1
9 10
3 10
0 10
8 9
1 5
|
19
|
|
5
|
10
1 1
2 2
2 0
4 2
4 0
2 0
0 2
4 0
4 2
5 1
|
6
|