Pelaat peliä, jossa kuljet $n$ kaupungin halki. Kaupungit on numeroitu $1,2,\ldots,n$. Sinun täytyy tuhota kaikki zombit kaupungissa $n$, jolloin pääset pelin läpi.

Halutessasi voit lisäksi pysähtyä missä tahansa kaupungissa matkan aikana ja tuhota siellä olevat zombit. Jos pysähdyt kaupungissa, sinun on tuhottava kaikki kyseisen kaupungin zombit.

Arvo $e$ kuvastaa, miten tehokas taistelija olet. Kaupungissa $k$ on $a_k$ zombia ja kunkin tuhoaminen vie aikaa $e$. Jos tuhoat kaupungin $k$ zombit, arvo $e$ on siitä lähtien $b_k$.

Kuinka kauan pelin läpäisy kestää, jos toimit optimaalisesti? Oletetaan, että kaupunkien välillä siirtyminen ei kuluta aikaa.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $e$: kaupunkien määrä ja tehokkuusarvo alussa.

Sitten syötteessä on $n$ kokonaislukua $a_1,a_2,\ldots,a_n$: montako zombia kussakin kaupungissa on. Kaikille arvoille $a_k$ ja $a_{k+1}$ pätee $a_k \le a_{k+1}$.

Sitten syötteessä on $n$ kokonaislukua $b_1,b_2,\ldots,b_n$: uusi tehokkuusarvo, jos tuhoat tietyn kaupungin zombit. Kaikille arvoille $b_k$ ja $b_{k+1}$ pätee $b_k \ge b_{k+1}$ ja lisäksi $e \ge b_1$.

Tuloste

Tulosta yksi kokonaisluku: kauanko pelin läpäisy vie aikaa.

Rajat

• $1 \le n \le 10^5$
• $1 \le e \le 10^6$
• $1 \le a_k \le 10^6$
• $1 \le b_k \le 10^6$

Esimerkki

Syöte:

3 5
2 3 10
4 2 1

Tuloste:

35

Selitys: tuhoat ensin zombit kaupungissa $2$ (aikaa kuluu $5 \cdot 3$) ja sitten kaupungissa $3$ (aikaa kuluu $2 \cdot 10$).