Рассмотрим лестницу, состоящую из \(n\) ступеней. Каждая ступень может быть целой или сломанной. Для каждой сломанной ступени задано целое число \(a_i\), обозначающее сложность ее ремонта.
Каждый день вы можете:
- либо отремонтировать произвольную сломанную ступеньку. Усилия, необходимые для ремонта \(i\)-й ступени, равны \(a_i\);
- либо отремонтировать две смежные сломанные ступеньки. Усилия, необходимые для ремонта \(i\)-й и \((i+1)\)-й ступени, равны \(2 \cdot (a_i+a_{i+1})\).
Вы хотите отремонтировать все сломанные ступени лестницы и сделать это за минимальное количество дней. Каково минимальное общее усилие, необходимое для ремонта всех сломанных ступеней за минимальное количество дней?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное возможное общее усилие, необходимое для ремонта всех сломанных ступеней за минимальное количество дней.
Примечание
В первом наборе входных данных вам ничего не нужно делать.
Во втором наборе входных данных вы можете отремонтировать \(3\)-ю и \(4\)-ю ступени в первый день, и \(2\)-ю ступень во второй день. Общее усилие будет равно \(2 \cdot (15 + 8) + 13 = 59\).
В третьем наборе входных данных вы можете отремонтировать \(4\)-ю ступень в первый день, и две первые ступени во второй день. Общее усилие будет равно \(8 + 2 \cdot (13 + 15) = 64\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
5
0 0 0 0 0
4
0 13 15 8
4
13 15 0 8
8
1 2 3 4 5 6 7 8
5
99999999 100000000 99999999 99999999 99999999
5
2 3 4 3 2
|
0
59
64
72
899999993
24
|