Fişierul intrare/ieşire:	scara3.in, scara3.out	Sursă	OJI 2005, clasele 11-12
Autor	Stelian Ciurea	Adăugată de	Paul-Dan Baltescu •pauldb
Timp execuţie pe test	0.05 sec	Limită de memorie	4736 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Scara 3

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.

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.

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.

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.

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

Exemplu

Cum se trimit solutii?