Dr. X 想从城市 0 出发前往城市 n。对于所有满足 0 \leq i \leq 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 \geq 1)，总飞行时间等于途经各段航线的飞行时间之和

f_i + f_{i+1} + \cdots + f_{i+j-1},

但这样一次连续飞行只算乘坐一次飞机。请计算 Dr. X 从城市 0 出发到达城市 n 所需的最少时间。

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

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

第三行包含 n 个空格分隔的整数 f_0, f_1, \cdots, 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 \leq 200。
• 对于 30\% 的数据，k = 1，n \leq 100,000。
• 对于另外 40\% 的数据，k \leq 100，n \leq 1,000。
• 对于 100\% 的数据，k \leq 1,000，n \leq 100,000，k \leq n，且 1 \leq g_i, f_i \leq 100,000。

2026年江苏省＂信息与未来＂小学生编程

江苏省赛2026