Анни устала выигрывать все контесты и получать бесконечный рейтинг, поэтому сегодня вместо контеста она поехала сажать картошку.
Участок Анни можно представить в виде бесконечной плоскости. Анни должна посадить $$$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$$$ единиц энергии.
Название |
---|