Есть \(n\) городов, пронумерованных от \(1\) до \(n\), красота города \(i\) равна \(a_i\).
Коммивояжёр хочет начать с города \(1\), посетить каждый город ровно один раз и вернуться в город \(1\).
Для всех \(i\ne j\), перелет из города \(i\) в город \(j\) стоит \(\max(c_i,a_j-a_i)\) долларов, где \(c_i\) — это нижний порог цены, наложенный на перелет городом \(i\). Обратите внимание, что здесь не берется абсолютное значение. Найдите минимальную общую стоимость поездки для коммивояжёра.
Выходные данные
Выведите единственное целое число — минимальную суммарную стоимость.
Примечание
В первом примере мы можем путешествовать в порядке \(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\), и мы не можем обойтись меньшим числом долларов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 9
2 1
4 1
|
11
|
|
2
|
6
4 2
8 4
3 0
2 3
7 1
0 1
|
13
|