该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小何被困在一个古老的地牢中。地牢呈 2 行 $n$ 列的网格状布局，每个格子都是一个房间。他需要在怪物追捕下迅速获得所有房间的情报才能逃脱。

题目描述

有一个 2 行 $n$ 列的网格状地牢，每个格子都是一个房间。小何最开始在左上角坐标为 $(1,1)$ 的房间，每次可以向上下左右四个方向中的任意一个相邻房间移动（如果存在的话）。但由于怪物紧随其后：

• 小何不能进入自己之前已经到过的房间；
• 小何不能进入当前房间的左侧房间（因为通道已被封堵）。

地牢中每个房间都有一个“复杂程度” $a_{i,j}$，表示小何亲自走到该房间并获得情报所需的时间（单位：秒），包括起点房间 $(1,1)$。到达一个房间即视为获得了该房间的情报。

在起点 $(1,1)$ 房间中，小何一开始就拥有 $k$ 个“探测道具”。每个道具可以在任意时刻使用，立即获取任意一个尚未获得情报的房间的信息，且不消耗时间。每个道具只能使用一次。

当小何获得了所有 $2n$ 个房间的情报后，便可安全逃脱。为了尽快脱身，他希望总耗时（即亲自走过的那些房间的 $a_{i,j}$ 之和）最小化。

请你计算小何最少需要多少时间才能逃脱。

输入格式

第一行两个整数 $n,k$，分别表示地牢的列数和小何持有的探测道具数。
接下来两行，每行包含 $n$ 个整数 $a_{i,j}$，表示每个房间的复杂程度（秒）。

输出格式

输出一个整数，表示小何逃脱所需的最少秒数。

样例

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

30

见 ex_path2.in

见 ex_path2.out

样例解释

在样例中，最优策略是使用两个道具分别探测房间 $(2,1)$ 和 $(1,3)$，让小何不必亲自前往这两个房间。
小何的行走路线为：右 → 下 → 右 → 右 → 上 → 右 → 下，总计经过房间的复杂程度之和

数据范围

• 对于前 20% 的数据，$k = 0$；
• 对于前 50% 的数据，$k \le 1$；
• 对于另外 10% 的数据，$k \ge 2n$；
• 对于另外 20% 的数据，$n \le 10$；
• 对于所有数据，$1 \le n \le 10^5$，$0 \le k \le 100$，$0 \le a_{i,j} \le 10^9$。