题目描述

一条实验轨道上设置了 $n$ 个采样位置，依次编号为 $1,2,\ldots,n$。研究员 Alice 和 Bob 分别拥有代价序列 $a_1,a_2,\ldots,a_n$ 与 $b_1,b_2,\ldots,b_n$。

两人需要交替完成共 $2k$ 次采样，由 Alice 先开始。

• Alice 每次采样时，需要选择一个不超过 $n$ 的位置 $x$，并且该位置编号必须严格大于她上一次选择的位置。选择后产生代价 $a_x$；
• Bob 每次采样时，需要选择一个不超过 $n$ 的位置 $x$。该位置编号必须严格大于他上一次选择的位置，同时不得小于 Alice 最近一次选择的位置。选择后产生代价 $b_x$。

在某位研究员第一次操作时，不受其“上一次选择的位置”的限制。

若轮到某位研究员操作时不存在任何合法位置，则实验立即失败，并将总代价记为 $10^{18}$。

Alice 和 Bob 会相互配合，使全部采样产生的总代价尽可能小。请计算能够得到的最小总代价。

输入格式

第一行两个整数 $n,k$，表示采样位置数量以及每位研究员需要进行的采样次数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示 Alice 在各位置采样的代价。

第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$，表示 Bob 在各位置采样的代价。

输出格式

一行一个整数表示最小分数和。

样例

样例输入1

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

样例输出1

32

样例输入2

10 6
60 8 63 72 1 100 23 59 71 59
81 27 66 53 46 64 86 27 41 82

样例输出2

472

数据范围与提示

保证对于所有的测试点满足以下限制：$1\leq k,n\leq 10^5,1\leq a_i,b_i\leq 10^9$。

特殊性质 A：$b_1\leq b_2\leq...\leq b_n$

特殊性质 B：存在一组最优解，使得第 $i$ 次选择的数字大于前 $i-1$ 次选择的数字。