← 返回题目列表

Codeforces · 802/M2

M2. 愚人节问题(中)

中文机器翻译题面 查看原题

土拨鼠需要准备 k HC 的问题2 结束 n 天。每个问题一旦准备好,就必须打印出来。

当天的一道题的准备 i (每天最多一次)费用 ai CHF,当天打印有问题 i (也最多每天一次)费用 bi 瑞士法郎。当然,在准备好问题之前不能打印问题(但在同一天做这两件事就可以了)。

准备和印刷的最低成本是多少?

输入

输入的第一行包含两个空格分隔的整数 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.