== include(page="template/taskheader" task_id="petreceri") ==

Dupa cum stiti Rick este un foarte mare iubitor de petreceri. Acesta cand merge la o petrecere mereu isi propune dinainte sa bea cel putin o anumita cantitate de alcool.

După cum ştiţi Rick este un foarte mare iubitor de petreceri. Acesta când merge la o petrecere mereu îşi propune dinainte să bea cel puţin o anumită cantitate de lapte.

Astazi si-a notat, in ordinea in care se intampla, N petreceri pe calendarul sau, fiecare dintre ele cu un numar a[i], numarul de unitati de alcool pe care vrea sa le consume la acea petrecere.

Astăzi şi-a notat, în ordinea în care se întâmplă, N petreceri pe calendarul său, fiecare dintre ele cu un număr a[i], numărul de unităţi de lapte pe care vrea să le consume la acea petrecere.

Cand a plecat spre prima dintre ele acesta a realizat ca si-a uitat tot alcoolul in alta dimensiune si tot ce are este sticla lui goala care poate tine T unitati de lichid. Acesta stie ca la fiecare petrecere o unitate de alcool costa c[i] bani (doar nu e prima oara cand a mers acolo) asa ca se intreaba care este numarul minim de bani pe care trebuie sa ii plateasca ca sa isi indeplineaca minimele propuse stiind ca intre petreceri acesta poate cara doar maxim T unitati de alcool in sticla sa.

Când a plecat spre prima dintre ele acesta a realizat că şi-a uitat tot laptele în altă dimensiune şi tot ce are este sticla lui goala care poate ţine T unităţi de lichid. Acesta ştie că la fiecare petrecere o unitate de lapte costă c[i] bani (doar nu e prima oara când a mers acolo) aşa că se întreabă care este numaărul minim de bani pe care trebuie sa îi plăteasca ca să îşi îndeplinească minimele propuse, ştiind că între petreceri acesta poate căra doar maxim T unităţi de lapte în sticla sa.

h2. Date de intrare

Prima linie a fisierului de intrare $petreceri.in$ contine numere N, si T. Pe urmatoarea linie apar N numere, al i-lea dintre ele fiind a[i]. Pe a treia linie apar N numere, al i-lea fiind c[i].

Prima linie a fişierului de intrare $petreceri.in$ contine numerele N, şi T. Pe următoarea linie apar N numere, al i-lea dintre ele fiind a[i]. Pe a treia linie apar N numere, al i-lea fiind c[i].

h2. Date de ieşire

Pe prima linie a fisierului $petreceri.out$ se va afisa suma minima de bani care trebuie platita ca Rick sa isi poate indeplini scopurile.

Pe prima linie a fişierului $petreceri.out$ se va afişa suma minimă de bani care trebuie platită ca Rick să îşi poată îndeplini scopurile.

h2. Restricţii

* Rick poate merge la petreceri doar in ordinea data, acesta nevrand sa utilizeze calatoria in timp.
* Rick poate cumpara alcool la inceputul, la finalul, sau oricand in timpul unei petreceri.
* $0 ≤ T ≤ 1000000000$ ?
* $0 ≤ N ≤ 1000000$ ?
* $0 ≤ a[i] ≤ T$
* $0 ≤ c[i] ≤ 1000000000$ ?
* Pentru teste in valoare de ? puncte $N, T ≤ 2000$
* Pentru alte teste in valoare de ? puncte $N ≤ 2000$ ?
* Pentru alte teste in valoare de ? punte $N, T ≤ 10000$

* Rick poate merge la petreceri doar în ordinea dată, acesta nevrând să utilizeze călătoria în timp.
* Rick poate cumpăra lapte la începutul, la finalul, sau oricând în timpul unei petreceri.
* $0 ≤ T ≤ 10^9^$
* $0 ≤ N ≤ 10^6^$
* $0 ≤ a[i] ≤ T$
* $0 ≤ c[i] ≤ 10^9^$
* Se garantează că soluţia o sa fie mai mică decât $10^18^$
* Pentru teste in valoare de 10 puncte $N, T ≤ 2000$
* Pentru alte teste in valoare de 20 de puncte $N ≤ 2000$
* Pentru alte teste in valoare de 30 de puncte $N ≤ 200000$
* Pentru alte teste in valoare de 40 de puncte nu există restricţii suplimentare
* *ATENŢIE! Având în vedere testele mari se recomandă parsarea fişierului petreceri.in. Puteţi folosi codul oferit de noi "aici":parsare-fisier-intrare (atât pentru utilizatorii de C++ şi sintaxă similară cu fstream, cât şi pentru iubitorii de C pur)*

h2. Exemplu
table(example). |_. petreceri.in |_. petreceri.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 2
  1 1 1 1 1
  1 2 3 4 5
| 8
|
| 10 11
  9 5 8 8 9 5 6 7 6 5
  6 9 6 9 9 9 5 5 5 7
| 417

|

| 18 19
  6 6 8 7 7 8 8 6 8 6 9 9 5 9 9 5 5 9
  6 8 7 6 7 7 9 5 7 7 5 8 7 5 5 6 8 7
| 704
|

h3. Explicaţie

...

În primul exemplu Rick îşi va cumpăra de la prima petrecere 1 unitate de lapte şi o va bea pe loc, şi îşi va mai cumpăra încă 2 la finalul petrecerii pentru a le lua cu el. La a doua petrecere va bea o unitate de lapte din sticlă şi îşi va cumpăra înca una de la bar. La a treia va face acelaşi lucru, plecând cu sticla plina. La ultimele 2 petreceri îşi va termina laptele din sticlă. Astfel Rick va cumpăra 3 unităţi de la prima petrecere, una de la a doua petrecere si una de la a treia plătind astfel 1+1+1+2+3 = 8 bani.

== include(page="template/taskfooter" task_id="petreceri") ==