UCPC農場には $N$ 個の杭が一列に打ち込まれている。これらの杭は高さがランダムに打ち込まれているため、美しく見えない。したがって、あなたは杭の高さを調整して、UCPC農場を美しく見せる必要がある。

各杭は左から右に $1$ から $N$ までの番号が付けられており、 $i$ 番目の杭の初期の高さは $H_i\text{ cm}$ である。また、各杭の材質は異なるため、各杭を引き上げたり打ち込んだりするのに必要な力はそれぞれ異なる。 $i$ 番目の杭を $1\text{ cm}$ 引き上げるには $A_i$ の力が、 $1\text{ 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\text{ cm}$ 引き上げるのに必要な力である $A_1, A_2, \dots, A_N$ が空白で区切られて与えられる。 ($1 \le A_i \le 20\,000$, $1 \le i \le N$)

その次の行には、各杭を $1\text{ 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