土拨鼠需要准备 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.