Есть \(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\).
Выведите единственное целое число — минимальную суммарную стоимость.
В первом примере мы можем путешествовать в порядке \(1\to 3\to 2\to 1\).
Общая стоимость составляет \(11\), и мы не можем обойтись меньшим числом долларов.
3 1 9 2 1 4 1
11
6 4 2 8 4 3 0 2 3 7 1 0 1
13
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач