Фермер Джон обнаружил, что его коровы дают больше молока, если занимаются спортом. Поэтому он послал N (1 <= N <= 25,000) своих коров взобраться на ближайшую гору и вернуться обратно.
Корове I требуется U(i) времени взобраться на гору и D(i) времени, чтобы спуститься с нее. Каждой корове нужна помощь человека, а их всего два ФД и его кузен фермер Дон (ФДо). ФД будет помогать коровам подниматься, а ФДо - спускаться. Поэтому в любой момент времени только одна корова будет подыматься (с помощью ФД) и не более одной коровы - спускаться (с помощью ФДо).
Группа коров может временно находится на вершине горы, если они туда взобрались, и ждут помощи от ФДо чтобы спуститься. Коровы могут спускаться в порядке, отличном от того, в котором они подымались.
Определите минимальное количество времени, которое требуется всем коровам, чтобы совершить полное путешествие туда и обратно.
PROBLEM NAME: climb
Формат входных данных
* Строка 1: Количество коров, N.
* Строки 2..1+N: Строка i+1 содержит два разделенных пробелом целых числа: U(i) и D(i). (1 <= U(i), D(i) <= 50,000).
Формат выходных данных
* Строка 1: Одно целое число, представляющее минимальное количество времени, которое требуется всем коровам взобраться на гору и вернуться обратно.
Примечание
Если корова 3 пойдет первой, затем корова 1 и затем корова 2 (и в таком же порядке возвращаться), это и даст суммарное время 17.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
6 4
8 1
2 3
|
17
|