Сурки должны подготовить k задач для HC2 за n дней. Каждую задачу нужно распечатать после того, как она будет подготовлена.
Подготовить задачу в день номер i (не более одной задачи в день) стоит ai CHF, а распечатать задачу в день i (тоже не более одной задачи в день) стоит bi CHF. Конечно, нельзя распечатать задачу до того, как она была подготовлена (но распечатать в тот же день, что и подготовить, позволительно).
Какова минимальная стоимость подготовки и распечатки всех задач?
Выходные данные
Выведите минимальную суммарную стоимость подготовки и печати k задач, которая равна минимально возможной сумме ai1 + ai2 + ... + aik + bj1 + bj2 + ... + bjk, где 1 ≤ i1 < i2 < ... < ik ≤ n, 1 ≤ j1 < j2 < ... < jk ≤ n и i1 ≤ j1, i2 ≤ j2, ..., ik ≤ jk.
Примечание
В примере одно из возможных решений — подготовить первую задачу в день 1 и распечатать ее в день 1, подготовить вторую задачу в день 2 и распечатать в день 4, подготовить третью задачу в день 3 и распечатать в день 5, подготовить четвертую задачу в день 6 и распечатать в день 8.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1
|
32
|