B4533 [信息与未来 2026] 旅行计划

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 解释 - 最快的方式是从城市 $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$。