CF802N April Fools' Problem (medium)

题目描述

旱獭们需要在 $n$ 天内为 HC $^{2}$ 准备 $k$ 道题。每道题准备好后还需要进行打印。

在第 $i$ 天准备题目（每天至多准备一道题）的花费为 $a_{i}$ 瑞士法郎，在第 $i$ 天打印题目（每天至多打印一道题）的花费为 $b_{i}$ 瑞士法郎。当然，题目不能在准备之前打印（但可以在同一天内完成准备和打印）。

请计算完成准备和打印 $k$ 道题所需的最小总费用。

输入格式

输入的第一行包含两个用空格分隔的整数 $n$ 和 $k$（$1 \leq k \leq n \leq 2200$）。
第二行包含 $n$ 个用空格分隔的整数 $a_{1},a_{2},\ldots,a_{n}$ —— 每天准备的费用。
第三行包含 $n$ 个用空格分隔的整数 $b_{1},b_{2},\ldots,b_{n}$ —— 每天打印的费用。

输出格式

输出准备和打印 $k$ 道题的最小总费用，即最小可能的 $a_{i_1} + a_{i_2} + \ldots + a_{i_k} + b_{j_1} + b_{j_2} + \ldots + b_{j_k}$，其中 $1 \leq i_1 < i_2 < \ldots < i_k \leq n$，$1 \leq j_1 < j_2 < \ldots < j_k \leq n$ 且 $i_1 \leq j_1$，$i_2 \leq j_2$，$\ldots$，$i_k \leq j_k$。

输入输出样例 #1

输入 #1

8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

输出 #1

32

说明/提示

在样例测试中，一种最优方案是：第一题在第 $1$ 天准备并于第 $1$ 天打印，第二题在第 $2$ 天准备并于第 $4$ 天打印，第三题在第 $3$ 天准备并于第 $5$ 天打印，第四题在第 $6$ 天准备并于第 $8$ 天打印。

由 ChatGPT 5 翻译