题目描述

Dr. X 想从城市 $0$ 出发前往城市 $n$。对于所有满足 $0 \le i \le n - 1$ 的整数 $i$，城市 $i$ 与城市 $i + 1$ 之间都有高铁和飞机两种出行方式：

• 坐高铁从城市 $i$ 到城市 $i + 1$ 花费的时间为 $g_i$；
• 坐飞机从城市 $i$ 到城市 $i + 1$ 花费的时间为 $f_i$。

然而，Dr. X 很害怕坐飞机，因此他希望整个行程中乘坐飞机的次数不得超过 $k$ 次。

为了减少坐飞机的次数，Dr. X 可以选择从城市 $i$ 直接飞到城市 $i + j$ ($j \ge 1$)，总飞行时间等于途经各段航线的飞行时间之和 $$\begin{aligned} f_i + f_{i+1} + \cdots + f_{i+j-1}, \end{aligned}$$ 但这样一次连续飞行 **只算乘坐一次飞机**。请计算 Dr. X 从城市 $0$ 出发到达城市 $n$ 所需的最少时间。

输入格式

输入第一行包含两个整数 $n$ 和 $k$，分别表示路线的数量和最多允许的坐飞机次数。

第二行包含 $n$ 个空格分隔的整数 $g_0, g_1, \ldots, g_{n-1}$，其中 $g_i$ 表示从城市 $i$ 坐高铁到城市 $i + 1$ 所花费的时间。

第三行包含 $n$ 个空格分隔的整数 $f_0, f_1, \ldots, f_{n-1}$，其中 $f_i$ 表示从城市 $i$ 坐飞机到城市 $i + 1$ 所花费的时间。

输出格式

输出一个整数，表示 Dr. X 从城市 $0$ 到达城市 $n$ 所需的最少时间。

输入输出样例 #1

输入 #1

3 1
4 6 8
1 11 4

输出 #1

14

输入输出样例 #2

输入 #2

3 2
4 6 8
1 11 4

输出 #2

11

输入输出样例 #3

输入 #3

3 1
4 6 8
1 7 4

输出 #3

12

说明/提示

样例 1 解释

• 最快的方式是从城市 $0$ 坐高铁到城市 $1$，再从城市 $1$ 坐高铁到城市 $2$，最后从城市 $2$ 坐飞机到城市 $3$，总耗时为 $4 + 6 + 4 = 14$。总共坐飞机 $1$ 次，满足限制。

样例 2 解释

• 最快的方式是从城市 $0$ 坐飞机到城市 $1$，从城市 $1$ 坐高铁到城市 $2$，从城市 $2$ 坐飞机到城市 $3$，总耗时为 $1 + 6 + 4 = 11$。总共坐飞机 $2$ 次。

样例 3 解释

• 尽管 $g_1 < f_1$，但在只能坐飞机 $1$ 次的情况下，最优方案是从城市 $0$ 直接飞到城市 $3$，总耗时为 $1 + 7 + 4 = 12$。

数据规模

• 对于 $10\%$ 的数据，$k = 1$，$n \le 200$。
• 对于 $30\%$ 的数据，$k = 1$，$n \le 100,000$。
• 对于另外 $40\%$ 的数据，$k \le 100$，$n \le 1,000$。
• 对于 $100\%$ 的数据，$k \le 1,000$，$n \le 100,000$，$k \le n$，且 $1 \le g_i, f_i \le 100,000$。