Na farmie UCPC znajduje się $N$ palików wbitych w jednym rzędzie. Paliki te mają losowe wysokości, przez co nie wyglądają estetycznie. Waszym zadaniem jest dostosowanie wysokości palików tak, aby farma UCPC wyglądała pięknie.

Każdy palik jest ponumerowany od lewej do prawej od $1$ do $N$, a początkowa wysokość $i$-tego palika wynosi $H_i$ cm. Ponadto, ponieważ materiały, z których wykonano paliki, są różne, siła wymagana do podniesienia lub wbicia każdego palika jest inna. Podniesienie $i$-tego palika o $1$ cm wymaga siły $A_i$, natomiast wbicie go o $1$ cm wymaga siły $B_i$.

Piękno farmy UCPC jest definiowane jako długość najdłuższego spójnego przedziału palików o tej samej wysokości. Znajdź minimalną siłę potrzebną do tego, aby piękno farmy UCPC wynosiło co najmniej $K$.

Rysunek E.1: Początkowy stan palików o pięknie równym 1

Rysunek E.2: Zwiększenie piękna do 3 kosztem włożonej siły

Wejście

W pierwszym wierszu podane są: liczba palików $N$ oraz wymagane piękno farmy UCPC $K$ ($1 \le N \le 100\,000$, $1 \le K \le N$).

W kolejnym wierszu podane są początkowe wysokości palików $H_1, H_2, \dots, H_N$, oddzielone spacjami ($1 \le H_i \le 100\,000$, $1 \le i \le N$).

W kolejnym wierszu podane są siły $A_1, A_2, \dots, A_N$ wymagane do podniesienia każdego palika o $1$ cm, oddzielone spacjami ($1 \le A_i \le 20\,000$, $1 \le i \le N$).

W kolejnym wierszu podane są siły $B_1, B_2, \dots, B_N$ wymagane do wbicia każdego palika o $1$ cm, oddzielone spacjami ($1 \le B_i \le 20\,000$, $1 \le i \le N$).

Wszystkie wartości podane na wejściu są liczbami całkowitymi.

Wyjście

W pierwszym wierszu należy wypisać minimalną siłę potrzebną do tego, aby piękno farmy UCPC wynosiło co najmniej $K$.

Przykład

Wejście 1

2 2
1 3
4 1
1 3

Wyjście 1

6

Wejście 2

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

Wyjście 2

5