Dans la ferme UCPC, $N$ piquets sont plantés en ligne. Ces piquets ont des hauteurs initiales aléatoires, ce qui n'est pas très esthétique. Vous devez donc ajuster les hauteurs des piquets pour rendre la ferme UCPC plus belle.

Chaque piquet est numéroté de $1$ à $N$ de gauche à droite, et la hauteur initiale du $i$-ème piquet est de $H_i$ cm. De plus, comme le matériau de chaque piquet est différent, la force requise pour soulever ou enfoncer chaque piquet varie. Soulever le $i$-ème piquet de $1$ cm nécessite une force de $A_i$, et l'enfoncer de $1$ cm nécessite une force de $B_i$.

La beauté de la ferme UCPC est définie comme la longueur du plus long segment contigu de piquets ayant tous la même hauteur. Trouvons la force minimale requise pour rendre la beauté de la ferme UCPC supérieure ou égale à $K$.

Figure E.1 : État initial des piquets avec une beauté de 1

Figure E.2 : Augmentation de la beauté à 3 en appliquant une force

Entrée

La première ligne contient le nombre de piquets $N$ et la beauté minimale souhaitée $K$ pour la ferme UCPC. ($1 \le N \le 100\,000$, $1 \le K \le N$)

La deuxième ligne contient les hauteurs initiales de chaque piquet $H_1, H_2, \dots, H_N$, séparées par des espaces. ($1 \le H_i \le 100\,000$, $1 \le i \le N$)

La troisième ligne contient la force nécessaire pour soulever chaque piquet de $1$ cm, $A_1, A_2, \dots, A_N$, séparées par des espaces. ($1 \le A_i \le 20\,000$, $1 \le i \le N$)

La quatrième ligne contient la force nécessaire pour enfoncer chaque piquet de $1$ cm, $B_1, B_2, \dots, B_N$, séparées par des espaces. ($1 \le B_i \le 20\,000$, $1 \le i \le N$)

Toutes les valeurs fournies en entrée sont des entiers.

Sortie

Affichez sur la première ligne la force minimale requise pour que la beauté de la ferme UCPC soit d'au moins $K$.

Exemples

Entrée 1

2 2
1 3
4 1
1 3

Sortie 1

6

Entrée 2

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

Sortie 2

5