G. Новое начало
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Анни устала выигрывать все контесты и получать бесконечный рейтинг, поэтому сегодня вместо контеста она поехала сажать картошку.

Участок Анни можно представить в виде бесконечной плоскости. Анни должна посадить $$$n$$$ кустов картошки, $$$i$$$-й куст должен быть посажен в точке $$$(x_i,y_i)$$$. Анни начнет в точке $$$(0, 0)$$$, и за один шаг будет перемещаться на одну единицу длины вправо или вверх (т. е. увеличивать свою координату $$$x$$$ или $$$y$$$ на $$$1$$$). Из любой точки $$$(X,Y)$$$ в процессе движения она может посадить любое количество кустов в любых точках плоскости, используя свою картофельную пушку. Для посадки одного куста в точку $$$(x,y)$$$ требуется $$$\max(|X-x|,|Y-y|)$$$ единиц энергии. Найдите минимальное количество энергии, необходимое для посадки всех кустов картошки.

Обратите внимание, что Анни может посадить любое количество кустов из любой точки.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 800\,000$$$).

Следующие $$$n$$$ строк содержат по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \le x_i,y_i \le 10^9$$$), определяющие требуемое положение $$$i$$$-го куста картошки. Возможно, некоторые кусты картошки требуется посадить в одно и то же место.

Выходные данные

Выведите минимальное количество энергии, необходимое для посадки всей картошки.

Примеры
Входные данные
2
1 1
2 2
Выходные данные
0
Входные данные
2
1 1
2 0
Выходные данные
1
Входные данные
3
5 5
7 7
4 9
Выходные данные
2
Входные данные
10
5 1
4 0
9 6
0 2
10 1
9 10
3 10
0 10
8 9
1 5
Выходные данные
19
Входные данные
10
1 1
2 2
2 0
4 2
4 0
2 0
0 2
4 0
4 2
5 1
Выходные данные
6
Примечание

В примере $$$1$$$ Анни может посетить все необходимые точки, поэтому энергия не требуется.

В примере $$$2$$$ Анни сначала может пойти в $$$(1,0)$$$, посадить оттуда второй куст, используя $$$1$$$ единицу энергии. Затем она пойдет в $$$(1,1)$$$ и посадит первый куст, используя $$$0$$$ единиц энергии.