基站选址

• 时间限制：3 秒
• 内存限制：128 MiB

题目描述

有 $N$ 个村庄坐落在一条直线上，第 $1$ 个村庄的位置为 $D_1=0$，其余村庄的位置依次为 $D_2,D_3,\ldots,D_N$。

你可以在这些村庄中建立不超过 $K$ 个通讯基站。在第 $i$ 个村庄建立基站的费用为 $C_i$。如果某个已建基站与第 $i$ 个村庄的距离不超过 $S_i$，则第 $i$ 个村庄被覆盖；否则需要支付补偿费用 $W_i$。

请选择基站位置，使建站费用与补偿费用之和最小。

输入格式

第一行包含两个整数 $N,K$。

第二行包含 $N-1$ 个整数 $D_2,D_3,\ldots,D_N$。

第三行包含 $N$ 个整数 $C_1,C_2,\ldots,C_N$。

第四行包含 $N$ 个整数 $S_1,S_2,\ldots,S_N$。

第五行包含 $N$ 个整数 $W_1,W_2,\ldots,W_N$。

输出格式

输出一个整数，表示最小总费用。

样例输入 1

3 2
1 2
2 3 2
1 1 0
10 20 30

样例输出 1

4

数据范围

对于所有数据，$1\le N\le20000$，$1\le K\le\min(N,100)$，$D_1=0<D_2<\cdots<D_N\le10^9$，$0\le C_i,W_i\le10^4$，$0\le S_i\le10^9$。