== include(page="template/taskheader" task_id="scara3") ==
Poveste si cerinta...
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 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
...
Fisierul de intrare $scara3.in$ contine:
* pe prima linie un numar natural $N$, reprezentand numarul total de trepte;
* pe cea de a doua linie un numar natural $K$, reprezentand numarul de trepte pe care se afla sticle cu apa;
* pe fiecare dintre urmatoarele $K$ linii cate doua numere naturale separate printr-un spatiu, reprezentand numarul de ordine al treptei pe care se afla o sticla cu apa si respectiv cantitatea de apa din acea sticla exprimata in decilitri;
* pe urmatoarea linie un numar natural $L$, reprezentand numarul de trepte pe care se afla sticle cu bautura energizanta;
* pe fiecare dintre urmatoarele $L$ linii cate doua numere naturale separate printr-un spatiu, reprezentand numarul de ordine al treptei pe care se afla o sticla cu bautura energizanta si respectiv cantitatea de bautura energizanta din acea sticla exprimata in decilitri.
h2. Date de iesire
...
Fisierul de iesire $scara3.out$ va contine o singura linie pe care vor fi scrise doua numere naturale $p$ $c$ separate printr-un spatiu, $p$ reprezentand numarul minim de pasi, iar $c$ suma minima cheltuita.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $N ≤ 1200$
* $0 ≤ K,L ≤ N$
* Cantitatea de apa aflata in oricare sticla este $1 ≤ x ≤ 1000$
* Cantitatea de bautura energizanta aflata in oricare sticla este $1 ≤ y ≤ 1000$
h2. Exemplu
table(example). |_. scara3.in |_. scara3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
1
1 2
2
4 1
1 2
| 3 2
|
h3. Explicatie
...
| 6
1
1 2
2
4 1
1 1
| 4 1
|
== include(page="template/taskfooter" task_id="scara3") ==
