批路（batc）

题目描述

Y 同学要按编号顺序处理 $n$ 个站点。一次批处理可以选择一段连续站点 $l,l+1,\ldots,r$，但长度不能超过 $k$。

若一次批处理从站点 $l$ 开始，到站点 $r$ 结束，它的代价为

其中 $e_i$ 是从第 $i$ 个站点启动的代价，$q_i$ 是在第 $i$ 个站点收尾的代价，$w_i$ 是从站点 $i$ 移动到站点 $i+1$ 的代价。请把 $1$ 到 $n$ 全部划分成若干批，使总代价最小。

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $e_1,e_2,\ldots,e_n$。

第三行包含 $n$ 个整数 $q_1,q_2,\ldots,q_n$。

第四行包含 $n-1$ 个整数 $w_1,w_2,\ldots,w_{n-1}$。当 $n=1$ 时这一行为空。

输出格式

输出一行一个整数，表示最小总代价。

样例

样例输入 #1

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

样例输出 #1

26

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le k\le n\le 2\times 10^5$，$1\le e_i,q_i,w_i\le 10^9$。