turnuri

Există $N$ turnuri numerotate de la $1$ la $N$. Fiecare turn $i$ cu $1 \leq i \leq N$ se află la coordonata întregă $P[i]$ și are înălțimea întreagă $H[i]$. Turnurile se află la coordonate distincte care respectă $P[1] < P[2] < \ldots < P[N]$.

Harap-Alb începe din turnul $1$ și vrea să ajungă în turnul $N$ prin salturi succesive înspre dreapta. De asemenea, se cunoaște puterea lui Harap-Alb, măsurată ca un număr $W \in \{1, 2\}$. Costul de a sări de la turnul $i$ la turnul $j$, unde $i < j$, este:

Ajutați-l pe Harap-Alb să calculeze costul minim pentru a ajunge din turnul $1$ în turnul $N$.

Date de intrare

Pe prima linie se află $N$ și $W$. Pe a doua linie se află $P[1], \ldots, P[N]$, iar pe a treia linie se află $H[1], \ldots, H[N]$. Numerele de pe fiecare linie sunt separate prin spații.

Date de ieșire

Pe prima linie se va afișa costul total minim pentru a ajunge de la turnul $1$ la turnul $N$.

Restricții

• $1 \leq N \leq 500 \ 000$
• $W \in \{1, 2\}$
• $1 \leq P[1] < P[2] < \ldots < P[N] \leq 10^9$
• $1 \leq H[i] \leq 10^9$ pentru $1 \leq i \leq N$
• Atenție! Rezultatul poate fi foarte mare (dar demonstrabil $\leq 10^{36}$), deci este nevoie de numere mari

Exemplu 1

stdin

4 1
1 3 4 10
5 100 4 3

stdout

39

Explicație

Pentru primul exemplu, comparând rutele, observăm că traseul optim este $1 \rightarrow 3 \rightarrow 4$:

• $1 \rightarrow 4: 45$
• $1 \rightarrow 3 \rightarrow 4 : (4−1) \times \text{max}(5,4) + (10−4) \times \text{max}(4,3) = 15 + 24 = 39$
• $1 \rightarrow 2 \rightarrow \ldots : (3-1) \times \text{max}(5,100) + \ldots \ge 200$

(Se observă ca orice rută care începe cu $1 \rightarrow 2$ este inoptimă)

Exemplu 2

stdin

2 2 
1 11
7 4

stdout

700

Explicație

Pentru al doilea exemplu, costul total este:

• $1 \rightarrow 2: (11-1)^2 \times \text{max}(7, 4) = 100 \times 7 = 700$.