opt

Buzdi a ajuns din greșeală în viitor, în anul 2040, în timpul Olimpiadei de Informatică, la clasa a VIII-a. Acesta a reușit să țină minte enunțul problemei și dorește sa vă propună această problemă mai devreme decât era în plan.

Cerința

Se consideră un sistem de coordonate $xOy$ și $N$ puncte în plan de coordonate numere naturale. Numim un poligon consecutiv un poligon format din două puncte consecutive și proiecțiile acestora pe dreapta $Ox$. Aria totală este egala cu suma tuturor ariilor poligoanelor consecutive.

O operație de Upgrade este definită ca fiind incrementarea coordonatei $Y$ cu $1$ a unui punct. Această operație poate fi:

• Folosită de maxim $K$ ori în total.
• Folosită de maxim $B_i$ ori pentru punctul $i \ (1 ≤ i ≤ N)$.

Dându-se cele $N$ puncte, $K$ si vectorul $B$, să se determine care este aria maximă totală ce poate fi obținută după aplicarea a maxim $K$ operații de Upgrade.

Date de intrare

Pe prima linie se găsesc numerele naturale $N$ și $K$ separate printr-un spațiu. Pe următoarele $N$ linii se găsesc două numere naturale $X_i$ și $Y_i$, separate printr-un spațiu, reprezentând coordonatele punctului de pe linia $i$. Pe ultima linie, se găsesc $N$ numere naturale, separate printr-un spațiu, reprezentând elementele vectorului $B$, cu semnificația din enunț.

Date de ieșire

Se va afișa un singur număr real cu o zecimala, reprezentând aria maximă totală ce poate fi obținută dupa aplicarea a maxim $K$ operații de Upgrade.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$.
• $0 \leq K \leq 100 \ 000 \ 000$.
• $0 \leq X_i, \ Y_i \leq 100 \ 000 \ 000, \ pentru \ 1 \leq i \leq N$.
• $X_i < X_{i+1}, \ pentru \ 1 \leq i < N$.
• $0 \leq B_i \leq 100 \ 000 \ 000, \ pentru \ 1 \leq i \leq N$.
• $B_1 \ + \ B_2 \ + \ B_3 \ + \ ... \ + \ B_N \leq 100 \ 000 \ 000$.
• Se consideră că un segment este un poligon cu arie 0.
• Pentru 17 puncte, $K = 0$.
• Pentru 22 puncte, $2 \leq N \leq 1 \ 000 \ și \ 1 \leq K \leq 1 \ 000$.

Exemplul

stdin

5 2
2 0
5 1
7 2
9 2
12 1
1 2 0 1 2

stdout

18.0

Explicație

Punctele albastre reprezintă punctele din datele de intrare, iar linia punctată reprezintă proiecția punctului respectiv.
Primul poligon consecutiv este format din primul punct $(2, 0)$ și al doilea punct $(5, 1)$ împreună cu proiecțiile lor pe $Ox$. Al doilea poligon consecutiv este format din al doilea punct $(5, 1)$ și al treilea punct $(7, 2)$ împreună cu proiecțiile lor pe $Ox$ și așa mai departe.
Putem să aplicăm operația de Upgrade pe al doilea punct și pe al patrulea punct, deoarece $B_2$ și $B_4$ nu sunt egale cu $0$. Aceste puncte vor fi acum $(5, 2)$ și $(9, 3)$, iar $B_2$ = $1$ și $B_4$ = $0$.
Aria totală este egală cu $A_1$ + $A_2$ + $A_3$ + $A_4$ + $A_5$ = $3$ + $4$ + $5$ + $6$ = $18$ ($A_i$ reprezintă aria poligonului consecutiv cu numărul $i$). Această arie este maximă posibilă.