gd

Axiom Postulates și-a instalat un nou joc și are nevoie de ajutor. Se dă o listă de $N$ niveluri, fiecare având o lungime $l_i$, în secunde, număr natural între $30$ și $300$. De asemenea, fiecare nivel are o dificultate, un alt număr natural $d_i$, cuprins între $1$ și $5$. Durata pentru a completa un astfel de nivel este egală cu $x_i * d_i * l_i$. Inițial, $x_i$ este egal cu $10$ pentru fiecare nivel.

În acest joc, Axiom are posibilitatea de a juca nivelurile în "Practice Mode". Pentru un nivel $i$, durata completării acestuia în "Practice Mode" este egală cu $2 * l_i$, iar, în urma acesteia, valoarea lui $x_i$ scade cu 3, dar nu poate deveni mai mică decât $1$.

Axiom Postulates se întreabă: dacă poate să se joace în "Practice Mode" de maxim $K$ ori, care este durata minimă pentru a completa toate nivelurile.

Date de intrare

Fișierul de intrare gd.in conține, pe prima linie, două numere naturale, $N$ și $K$. Pe cea de-a doua linie sunt $N$ numere naturale, reprezentând lungimile în secunde ale nivelelor, iar, pe a treia linie, alte $N$ numere naturale, reprezentând dificultățile nivelelor.

Date de ieșire

Fișierul de ieșire gd.out conține un singur număr natural, reprezentând durata minimă pentru a completa toate nivelurile.

Restricții și precizări

• $1 \le N \le 10\ 000\ 000$
• $0 \le K \le 30\ 000\ 000$
• $30 \le l_i \le 300$
• $1 \le d_i \le 5$

Exemplul 1

gd.in

4 0
100 200 50 70
1 2 5 2

gd.out

8900

Explicație

Avem $K = 0$, așadar niciun nivel nu va fi jucat în „Practice Mode”. Toate nivelurile vor fi jucate normal, având coeficientul inițial $x_i = 10$. Prin urmare, durata totală pentru a termina toate nivelurile va fi:

$10 \cdot 1 \cdot 100 + 10 \cdot 2 \cdot 200 + 10 \cdot 5 \cdot 50 + 10 \cdot 2 \cdot 70 = 1000 + 4000 + 2500 + 1400 = 8900 \text{ secunde.}$

Exemplul 2

gd.in

3 4
150 40 30
1 3 2

gd.out

2310

Explicație

Avem la dispoziție $K = 4$ exersări în „Practice Mode”. Repartizarea optimă a exersărilor pentru a minimiza timpul, precum și calculul duratelor per nivel, sunt ilustrate în figura de mai jos: $N =3,K =4$, rezultat = $2310$ secunde