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