Задача #bav0001

Задача продублирована во вложении в pdf

Как известно, Никита очень любит апельсины. Мир, в котором живет Никита, представляет собой числовую прямую, на которой расположены n деревьев с апельсинами. Дерево с номером i имеет координату xi, и апельсины на нем созревают в момент времени ti. Известно, что все координаты деревьев попарно различны.

Изначальная координата Никиты равна 0. Двигаясь на одну единицу по числовой прямой, у Никиты копится одна единица гнева.

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

Найдите минимальный итоговый гнев Никиты, чтобы съесть все апельсины и вернуться в координату 0.

Формат входных данных:

Первая строка содержит одно целое число n (1≤n≤200000) — количество деревьев с апельсинами.

Следующие n строк содержат два целых числа xi и ti (−109≤xi≤109, 1≤ti≤n, xi≠0) — координата i-го дерева и момент созревания на нем апельсинов.

Гарантируется, что в координате 0 нет дерева и что все координаты деревьев попарно различны.

Формат выходных данных

Выведите минимальный итоговый гнев Никиты, когда он съест все апельсины и вернется в изначальную координату.

Примеры

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

5

2 1

1 4

5 1

4 4

3 2

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

12

Примечания

Рассмотрим пример из условия. Один из оптимальных маршрутов Никиты выглядит так:

В момент времени 0 Никита находится в координате 0, и накопил 0 гнева.

В момент времени 1 появляются апельсины в координатах 2 и 5. Никита съедает сначала апельсин в координате

2, а затем в координате 5. В итоге Никита оказывается в координате 5, и он накопил 5 гнева.

В момент времени 2 появляется апельсин в координате 3. Никита идет за ним и съедает, теперь он в координате 3, и у него 7 единиц гнева.

В момент времени 4 появляются апельсины в координатах 1 и 4. Никита сначала идет за апельсином в координате 4, затем за апельсином в координате 1, и затем возвращается в координату 0. Итого, Никита накопил 7+(4−3)+(4−1)+(1−0)=7+1+3+1=12 единиц гнева.