Dr. X 想从城市 0 出发前往城市 n。对于所有满足 0 ≤ i ≤ n − 1 的整数 i，城市 i 与城市 i + 1
之间都有高铁和飞机两种出行方式：
坐高铁从城市 i 到城市 i + 1 花费的时间为 gi；
坐飞机从城市 i 到城市 i + 1 花费的时间为 fi。
然而，Dr. X 很害怕坐飞机，因此他希望整个行程中乘坐飞机的次数不得超过 k 次。
为了减少坐飞机的次数，Dr. X 可以选择从城市 i 直接飞到城市 i + j (j ≥ 1)，总飞行时间等于
途经各段航线的飞行时间之和
fi + fi+1 + ⋯ + fi+j−1,
但这样一次连续飞行只算乘坐一次飞机。请计算 Dr. X 从城市 0 出发到达城市 n 所需的最少时
间。
输入第一行包含两个整数 n 和 k，分别表示路线的数量和最多允许的坐飞机次数。
第二行包含 n 个空格分隔的整数 g0, g1,…, gn−1，其中 gi 表示从城市 i 坐高铁到城市 i + 1 所
花费的时间。
第三行包含 n 个空格分隔的整数 f0, f1,…, fn−1，其中 fi 表示从城市 i 坐飞机到城市 i + 1 所
花费的时间。
输出一个整数，表示 Dr. X 从城市 0 到达城市 n 所需的最少时间。
样例输⼊ 2
3 2
4 6 8
1 11 4
样例输出 2
11
最快的方式是从城市 0 坐飞机到城市 1，从城市 1 坐高铁到城市 2，从城市 2 坐飞机到城
市 3，总耗时为 1 + 6 + 4 = 11。总共坐飞机 2 次。
样例输⼊ 3
3 1
4 6 8
1 7 4
样例输出 3
12
尽管 g1 < f1，但在只能坐飞机 1 次的情况下，最优方案是从城市 0 直接飞到城市 3，总
耗时为 1 + 7 + 4 = 12。
数据规模
对于 10% 的数据，k = 1，n ≤ 200。
对于 30% 的数据，k = 1，n ≤ 100, 000。
对于另外 40% 的数据，k ≤ 100，n ≤ 1, 000。
对于 100% 的数据，k ≤ 1, 000，n ≤ 100, 000，k ≤ n，且 1 ≤ gi, fi ≤ 100, 000。