En la granja UCPC, hay $N$ estacas clavadas en una fila. Estas estacas tienen alturas aleatorias, por lo que no se ven hermosas. Por lo tanto, debes ajustar las alturas de las estacas para que la granja UCPC se vea hermosa.

Cada estaca está numerada de izquierda a derecha de $1$ a $N$, y la altura inicial de la $i$-ésima estaca es $H_i$ cm. Además, debido a que los materiales de cada estaca son diferentes, la fuerza requerida para levantar o clavar cada estaca varía. Levantar la $i$-ésima estaca $1$ cm requiere una fuerza de $A_i$, y clavar la $i$-ésima estaca $1$ cm requiere una fuerza de $B_i$.

La belleza de la granja UCPC se define como la longitud del segmento contiguo más largo de estacas que tienen la misma altura. Calculemos la fuerza mínima requerida para hacer que la belleza de la granja UCPC sea al menos $K$.

Figura E.1: Estado inicial de las estacas con belleza 1

Figura E.2: Estado después de aplicar fuerza para aumentar la belleza a 3

Entrada

La primera línea contiene el número de estacas $N$ y la belleza $K$ que debe cumplir la granja UCPC, separados por un espacio. ($1 \le N \le 100\,000$, $1 \le K \le N$)

La siguiente línea contiene las alturas iniciales de cada estaca, $H_1, H_2, \dots, H_N$, separadas por espacios. ($1 \le H_i \le 100\,000$, $1 \le i \le N$)

La siguiente línea contiene la fuerza necesaria para levantar cada estaca $1$ cm, $A_1, A_2, \dots, A_N$, separadas por espacios. ($1 \le A_i \le 20\,000$, $1 \le i \le N$)

La siguiente línea contiene la fuerza necesaria para clavar cada estaca $1$ cm, $B_1, B_2, \dots, B_N$, separadas por espacios. ($1 \le B_i \le 20\,000$, $1 \le i \le N$)

Todos los valores de la entrada son enteros.

Salida

Imprime en la primera línea la fuerza mínima necesaria para que la belleza de la granja UCPC sea al menos $K$.

Ejemplos

Entrada Ejemplo 1

2 2
1 3
4 1
1 3

Salida Ejemplo 1

6

Entrada Ejemplo 2

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

Salida Ejemplo 2

5