Во время археологических раскопок были обнаружены руины античного храма. Лучше всего сохранилась колоннада, состоящая из $$$n$$$ колонн, расположенных в ряд. Все колонны частично разрушились, поэтому оказалось, что высоты всех колонн различны. Высота $$$i$$$-й колонны равна $$$h_i$$$.

Чтобы предотвратить дальнейшее разрушение колонн из-за непогоды, было принято решение накрыть их крышами. Каждая крыша располагается горизонтально и одним концом прикрепляется к верху некоторой колонны. Можно установить крышу, которая накрывает отрезок колонн с $$$i$$$-й по $$$j$$$-ю ($$$1 \leq i \leq j \leq n$$$), если выполнено одно из следующих условий:

• Если $$$i$$$-я колонна выше всех остальных на отрезке $$$[i, j]$$$, то можно закрепить крышу левым концом на $$$i$$$-й колонне.
• Если $$$j$$$-я колонна выше всех остальных на отрезке $$$[i, j]$$$, то можно закрепить крышу правым концом на $$$j$$$-й колонне.

Наверху каждой колонны можно закрепить не более одной крыши. Стоимость закрепления крыши на $$$i$$$-й колонне равна $$$c_i$$$ вне зависимости от того, направлена она влево или вправо и сколько колонн накрывает.

Требуется закрепить крыши на некоторых колоннах таким образом, чтобы каждая колонна была накрыта хотя бы одной крышей, и суммарная стоимость была минимальна.