题目描述

UCPC 农场中有 $N$ 根木桩排成一列。由于这些木桩的高度杂乱无章，看起来并不美观。你需要调整木桩的高度，使农场变得更加美观。

木桩从左到右编号为 $1$ 到 $N$。第 $i$ 根木桩的初始高度为 $H_i$ 厘米。由于每根木桩的材质不同，调整它们所需的力也不同：

• 将第 $i$ 根木桩升高 $1$ 厘米需要消耗 $A_i$ 单位的力；
• 将第 $i$ 根木桩降低 $1$ 厘米需要消耗 $B_i$ 单位的力。

农场的美观度定义为：由高度完全相同的木桩组成的最长连续区间的长度。

请计算将农场的美观度变为至少 $K$ 所需消耗的最小总力。

图 E.1：一种美观度为 1 的初始状态示意图。

图 E.2：通过调整高度，使连续 3 根木桩等高。

输入格式

第一行包含两个整数 $N,K$，分别表示木桩数量和要求达到的最低美观度。$(1\le N\le 100000,\ 1\le K\le N)$

第二行包含 $N$ 个整数 $H_1,H_2,\ldots,H_N$，表示各木桩的初始高度。$(1\le H_i\le 100000)$

第三行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$，表示将各木桩升高 $1$ 厘米所需的力。$(1\le A_i\le 20000)$

第四行包含 $N$ 个整数 $B_1,B_2,\ldots,B_N$，表示将各木桩降低 $1$ 厘米所需的力。$(1\le B_i\le 20000)$

输入中的所有数均为整数。

输出格式

输出一个整数，表示使农场美观度达到至少 $K$ 所需的最小总力。

样例

输入样例 1

2 2
1 3
4 1
1 3

输出样例 1

6

输入样例 2

5 3
1 2 3 2 1
1 3 1 3 4
1 3 5 3 1

输出样例 2

5