扁平化最短路（path）

题目描述

有一个 $2$ 行 $n$ 列的网格状地牢，每个格子都是一个房间，你最开始在左上角坐标为 $(1,1)$ 的房间，每次可以走向当前所在房间的相邻房间（如果存在的话）。

但是地牢显然不是旅游景点，里面充满了危险。你身后随时有怪物追逐，因此你不能走进你以前已经进入过的房间；同时怪物也会封堵你的逃跑路线，因此你不能进入当前房间左侧的房间。

然而也并不是无法逃脱，只要你了解了整个地牢的结构，你就能安全离开这里。

每个房间有一个复杂程度 $a_{i,j}$，表示你经过这个房间需要花费的时间（包括出发点的 $(1,1)$ 房间），你经过一个房间后就会获取这个房间的情报。

在 $(1,1)$ 房间中有 $k$ 个道具，每个道具使用后可以立刻获取任何一个房间的情报。你可以在到达 $(1,1)$ 后的任何时候使用它们，但是每个道具只能使用一次。

• 即你在到达起点，站在起点 $(1,1)$ 格子后，就获得了 $k$ 个道具，在此后的任意一个时间节点，都可以使用这些道具。

当你获取了所有 $2n$ 个房间的情报后，你就可以成功逃脱。

为了防止被追上，动作自然越快越好，那么，你最少需要多少时间才能逃脱？

输入格式

第一行两个整数 $n,k$，表示地牢的列数和持有的道具数。

接下来两行每行 $n$ 个整数 $a_{i,j}$，表示探明对应房间情报所需要的秒数。

输出格式

一行一个整数，表示逃脱需要的最少秒数。

样例 #1

样例输入 #1

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

样例输出 #1

30

提示

样例 1 解释

对于样例，最优的解决方法是使用道具探明 $(2,1),(1,3)$ 两个房间。

出发后的行走方向为：右下右右上右下，总时间为 $9+5+6+1+3+4+2+0=30$。

数据范围

对于前 $20\%$ 的数据，$k=0$。

对于前 $50\%$ 的数据，$k\le 1$。

对于另外 $10\%$ 的数据，$k\ge 2n$。

对于另外 $20\%$ 的数据，$n\le 10$。

对于 $100\%$ 的数据，$1\le n\le 10^5, 0\le k \le 100, 0\le a_{i,j} \le10^9$。