UCPC 农场里排着一列共 $N$ 个木桩。这些木桩的高度是随机的，看起来并不美观。因此，你需要通过调整木桩的高度，使 UCPC 农场看起来更美观。

每个木桩从左到右依次编号为 $1$ 到 $N$，第 $i$ 个木桩的初始高度为 $H_i$ cm。此外，由于每个木桩的材质不同，拉高或砸低每个木桩所需的力气也各不相同。将第 $i$ 个木桩拉高 $1$ cm 需要消耗 $A_i$ 的力气，而将其砸低 $1$ cm 需要消耗 $B_i$ 的力气。

UCPC 农场的“美观度”定义为由高度相同的木桩组成的最长连续区间的长度。求为了使 UCPC 农场的美观度达到 $K$ 或以上，所需要消耗的最小力气。

图 E.1：美观度为 1 的初始木桩状态

图 E.2：消耗力气将美观度提升至 3 的过程

输入格式

第一行给出木桩的数量 $N$ 和需要满足的 UCPC 农场的美观度 $K$。($1 \le N \le 100\,000$, $1 \le K \le N$)

第二行给出每个木桩的初始高度 $H_1, H_2, \dots, H_N$，用空格分隔。($1 \le H_i \le 100\,000$, $1 \le i \le N$)

第三行给出将每个木桩拉高 $1$ cm 所需的力气 $A_1, A_2, \dots, A_N$，用空格分隔。($1 \le A_i \le 20\,000$, $1 \le i \le N$)

第四行给出将每个木桩砸低 $1$ cm 所需的力气 $B_1, B_2, \dots, B_N$，用空格分隔。($1 \le B_i \le 20\,000$, $1 \le i \le N$)

输入中给出的所有值均为整数。

输出格式

输出一行，表示使 UCPC 农场的美观度达到 $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