C. Задача коммивояжёра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ городов, пронумерованных от $$$1$$$ до $$$n$$$, красота города $$$i$$$ равна $$$a_i$$$.

Коммивояжёр хочет начать с города $$$1$$$, посетить каждый город ровно один раз и вернуться в город $$$1$$$.

Для всех $$$i\ne j$$$, перелет из города $$$i$$$ в город $$$j$$$ стоит $$$\max(c_i,a_j-a_i)$$$ долларов, где $$$c_i$$$ — это нижний порог цены, наложенный на перелет городом $$$i$$$. Обратите внимание, что здесь не берется абсолютное значение. Найдите минимальную общую стоимость поездки для коммивояжёра.

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

В первой строке содержится одно целое $$$n$$$ ($$$2\le n\le 10^5$$$) — количество городов.

В $$$i$$$-й из следующих $$$n$$$ строк содержится по два целых числа $$$a_i$$$, $$$c_i$$$ ($$$0\le a_i,c_i\le 10^9$$$) — красота и нижний порог цены города $$$i$$$.

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

Выведите единственное целое число — минимальную суммарную стоимость.

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

В первом примере мы можем путешествовать в порядке $$$1\to 3\to 2\to 1$$$.

  • Рейс $$$1\to 3$$$ стоит $$$\max(c_1,a_3-a_1)=\max(9,4-1)=9$$$.
  • Рейс $$$3\to 2$$$ стоит $$$\max(c_3, a_2-a_3)=\max(1,2-4)=1$$$.
  • Рейс $$$2\to 1$$$ стоит $$$\max(c_2,a_1-a_2)=\max(1,1-2)=1$$$.

Общая стоимость составляет $$$11$$$, и мы не можем обойтись меньшим числом долларов.