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