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

Domnul G are de urcat o scara cu $N$ trepte. In mod normal, la fiecare pas pe care il face, el urca o treapta. Pe $K$ dintre aceste trepte se afla cate o sticla cu un numar oarecare de decilitri de apa, fie acesta $x$. Daca bea toata apa dintr-o astfel de sticla, forţa si mobilitatea lui G cresc, astfel încat, la urmatorul pas el poate urca pana la x trepte, după care, daca nu bea din nou ceva, revine la "normal". Sticlele cu apa nu costa nimic. Cantitatea de apa continuta de aceste sticle poate sa difere de la o treapta la alta.
Pe $L$ trepte se afla cate o sticla cu bautura energizanta. Si pentru aceste sticle, cantitatea de bautura energizanta poate sa difere de la o treapta la alta. Sa presupunem ca intr-una dintre aceste sticle avem $y$ decilitri de bautura energizanta. Dacă bea $q$ ({$q≤y$})  decilitri dintr-o astfel de sticla, la urmatorul pas G poate urca pana la $2q$ trepte, dupa care si in acest caz, daca nu bea din nou ceva, el revine la "normal". Insa bautura energizanta costa: pentru o cantitate de $q$ decilitri consumati, G trebuie sa plateasca $q$ lei grei.

Domnul G are de urcat o scara cu $N$ trepte. In mod normal, la fiecare pas pe care il face, el urca o treapta. Pe $K$ dintre aceste trepte se afla cate o sticla cu un numar oarecare de decilitri de apa, fie acesta $x$. Daca bea toata apa dintr-o astfel de sticla, forta si mobilitatea lui G cresc, astfel incat, la urmatorul pas el poate urca pana la x trepte, dupa care, daca nu bea din nou ceva, revine la "normal". Sticlele cu apa nu costa nimic. Cantitatea de apa continuta de aceste sticle poate sa difere de la o treapta la alta.
Pe $L$ trepte se afla cate o sticla cu bautura energizanta. Si pentru aceste sticle, cantitatea de bautura energizanta poate sa difere de la o treapta la alta. Sa presupunem ca intr-una dintre aceste sticle avem $y$ decilitri de bautura energizanta. Daca bea $q$ $(q ≤ y)$  decilitri dintr-o astfel de sticla, la urmatorul pas G poate urca pana la $2q$ trepte, dupa care si in acest caz, daca nu bea din nou ceva, el revine la "normal". Insa bautura energizanta costa: pentru o cantitate de $q$ decilitri consumati, G trebuie sa plateasca $q$ lei grei.

Pot exista trepte pe care nu se afla nici un pahar, dar si trepte pe care se afla atat o sticla cu apa cat si una cu bautura energizanta. In astfel de situatii, nu are rost ca G sa bea ambele bauturi deoarece efectul lor nu se cumuleaza; el poate alege sa bea una dintre cele doua bauturi sau poate sa nu bea nimic.
h2. Cerinta

Determinati $p$, numarul minim de pasi pe care trebuie sa ii facă G pentru a urca scara, precum si suma minima pe care trebuie sa o cheltuiasca G pentru a urca scara in $p$ pasi.

 
Determinati $p$, numarul minim de pasi pe care trebuie sa ii faca G pentru a urca scara, precum si suma minima pe care trebuie sa o cheltuiasca G pentru a urca scara in $p$ pasi.

h2. Date de intrare