Монокарп очень долго коллекционировал разные журналы и теперь решил их продать. Для этого он выставил в ряд \(n\) коробок с журналами, причем в \(i\)-й коробке находится \(a_i\) журналов. Некоторые из коробок он накрыл крышками.
Внезапно пошел дождь, и Монокарпу нужно спасти от дождя как можно большее количество журналов. Для этого он может сделать следующее: если коробка \(i\) изначально была накрыта крышкой, он может либо переместить крышку с коробки \(i\) на коробку \((i-1)\) (если она есть), либо оставить крышку на коробке \(i\). Считайте, что все перемещения крышек Монокарп выполнит мгновенно, и каждая крышка будет перемещена не более одного раза. Журналы, которые после перемещения будут находиться в коробках с крышками, будут спасены от дождя; все остальные журналы намокнут.
Перед вами стоит задача определить максимальное количество журналов, которые Монокарп может спасти от дождя.
Выходные данные
На каждый набор входных данных выведите максимальное количество журналов, которые Монокарп может спасти от дождя.
Примечание
В первом наборе входных данных в примере нужно переместить крышку со второй коробки влево на первую коробку. Тогда коробки \(1\), \(3\) и \(4\) будут накрыты крышками, и \(10 + 8 + 9 = 27\) журналов будут спасены от дождя.
Во втором наборе входных данных нужно переместить крышку со второй коробки на первую коробку, крышку с третьей коробки на вторую коробку, крышку с пятой коробки на четвертую коробку, крышку с шестой коробки на пятую коробку. Тогда коробки \(1\), \(2\), \(4\) и \(5\) будут накрыты крышками, и \(20 + 10 + 30 + 20 = 80\) журналов будут спасены от дождя.
В третьем наборе входных данных нет ни одной крышки, поэтому ни один из журналов нельзя спасти от дождя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
01110
10 5 8 9 6
6
011011
20 10 9 30 20 19
4
0000
100 100 100 100
4
0111
5 4 5 1
|
27
80
0
14
|