Задача №115301. Крыши
Во время археологических раскопок были обнаружены руины античного храма. Лучше всего сохранилась колоннада, состоящая из \(n\) колонн, расположенных в ряд. Все колонны частично разрушились, поэтому оказалось, что высоты всех колонн различны. Высота \(i\)-й колонны равна \(h_i\).
Чтобы предотвратить дальнейшее разрушение колонн из-за непогоды, было принято решение накрыть их крышами. Каждая крыша располагается горизонтально и одним концом прикрепляется к верху некоторой колонны. Можно установить крышу, которая накрывает отрезок колонн с \(i\)-й по \(j\)-ю (\(1 \leq i \leq j \leq n\)), если выполнено одно из следующих условий:
- Если \(i\)-я колонна выше всех остальных на отрезке \([i, j]\), то можно закрепить крышу левым концом на \(i\)-й колонне.
- Если \(j\)-я колонна выше всех остальных на отрезке \([i, j]\), то можно закрепить крышу правым концом на \(j\)-й колонне.
Наверху каждой колонны можно закрепить не более одной крыши. Стоимость закрепления крыши на \(i\)-й колонне равна \(c_i\) вне зависимости от того, направлена она влево или вправо и сколько колонн накрывает.
Требуется закрепить крыши на некоторых колоннах таким образом, чтобы каждая колонна была накрыта хотя бы одной крышей, и суммарная стоимость была минимальна.
В первой строке находится число \(n\) (\(1 \le n \le 200\,000\)) — количество колонн.
Во второй строке даны \(n\) целых чисел \(h_1, h_2, \ldots, h_n\) (\(1 \leq h_i \leq 10^9\)) — высоты колонн. Гарантируется, что все \(h_i\) различны.
В третьей строке даны \(n\) целых чисел \(c_1, c_2, \ldots, c_n\) (\(1 \leq c_i \leq 10^9\)) — стоимости закрепления крыш на колонных.
Выведите одно число — минимальную стоимость накрыть все колонны крышами.
3 3 10 7 2 5 2
7
1 5 2
2