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).