Amr живет в Лалаландии. Лалаландия — очень красивая страна, расположенная на координатной прямой. Лалаландия славится своими яблонями — в стране они растут везде.
Всего в Лалаландии ровно n яблонь. Яблоня номер i расположена в точке xi, на ней растет ai яблок. Amr хочет собрать яблоки с этих яблонь. Amr сейчас стоит в точке x = 0. Сначала он выбирает, вправо ли он пойдёт или влево. Он будет следовать в этом направлении, пока не дойдет до первой яблони. Он соберет с этой яблони все яблоки, а затем пойдет в противоположном направлении и будет идти, пока не дойдет до первой непосещённой яблони, снова развернётся, и так далее. Иными словами, посещая каждую новую яблоню, Amr разворачивается и идёт в противоположном направлении. Amr перестанет собирать яблоки, когда в направлении его движения не останется ни одной непосещённой яблони.
Какое максимальное количество яблок он сможет собрать?
Выходные данные
Выведите максимальное количество яблок, которое может собрать Amr.
Примечание
В первом тесте не имеет значения, пойдет ли Amr сначала влево или вправо. В обоих случаях он соберет все яблоки.
Во втором тесте оптимальное решение таково: пойти влево до x = - 1, собрать там яблоки, развернуться, затем дойти до x = 1, собрать там яблоки, развернуться, и дойти до последнего дерева x = - 2.
В третьем тесте оптимальное решение таково: пойти вправо до x = 1, собрать там яблоки, развернуться, после чего Amr больше не может собирать яблоки, так как слева от него нет яблонь.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
-1 5
1 5
|
10
|
|
2
|
3
-2 2
1 4
-1 3
|
9
|
|
3
|
3
1 9
3 5
7 10
|
9
|