scara

Domnul G are de urcat o scară cu $n$ trepte. În mod normal, la fiecare pas pe care îl face, el urcă o treaptă. Pe $k$ dintre aceste trepte se află câte o sticlă cu un număr oarecare de decilitri de apă, fie acesta $x$. Dacă bea toată apa dintr-o astfel de sticlă, forţa şi mobilitatea lui G cresc, astfel încât, la următorul pas el poate urca până la $x$ trepte, după care, dacă nu bea din nou ceva, revine la “normal”. Sticlele cu apă nu costă nimic. Cantitatea de apă conţinută de aceste sticle poate să difere de la o treaptă la alta.

Pe $j$ trepte se află câte o sticlă cu băutura energizantă. Şi pentru aceste sticle, cantitatea de băutură energizantă poate să difere de la o treaptă la alta. Să presupunem că într-una dintre aceste sticle avem $y$ decilitri de băutură energizantă. Dacă bea $q$ ($q≤y$) decilitri dintr-o astfel de sticlă, la următorul pas G poate urca până la $2q$ trepte, după care şi în acest caz, dacă nu bea din nou ceva, el revine la “normal”. Însă băutura energizantă costă: pentru o cantitate de $q$ decilitri consumaţi, G trebuie să plătească $q$ lei grei.

Pot exista trepte pe care nu se află nici un pahar, dar şi trepte pe care se află atât o sticlă cu apă cât şi una cu băutură energizantă. În astfel de situaţii, nu are rost ca G să bea ambele băuturi deoarece efectul lor nu se cumulează; el poate alege să bea una dintre cele două băuturi sau poate să nu bea nimic.

Cerinţă

Determinaţi $p$, numărul minim de paşi pe care trebuie să îi facă G pentru a urca scara, precum şi suma minimă pe care trebuie să o cheltuiască G pentru a urca scara în $p$ paşi.

Date de intrare

Fişierul text de intrare scara.in conţine:

• pe prima linie un număr natural $n$, reprezentând numărul total de trepte;
• pe cea de a doua linie un număr natural $k$, reprezentând numărul de trepte pe care se află sticle cu apă;
• pe fiecare dintre următoarele $k$ linii câte două numere naturale separate printr-un spaţiu, reprezentând numărul de ordine al treptei pe care se află o sticlă cu apă şi respectiv cantitatea de apă din acea sticlă exprimată în decilitri;
• pe următoarea linie un număr natural $j$, reprezentând numărul de trepte pe care se află sticle cu băutură energizantă;
• pe fiecare dintre următoarele $j$ linii câte două numere naturale separate printr-un spaţiu, reprezentând numărul de ordine al treptei pe care se află o sticlă cu băutură energizantă şi respectiv cantitatea de băutură energizantă din acea sticlă exprimată în decilitri.

Date de ieşire

Fişierul text de ieşire scara.out va conţine o singură linie pe care vor fi scrise două numere naturale $p c$ separate printr-un spaţiu, $p$ reprezentând numărul minim de paşi, iar $c$ suma minimă cheltuită.

Restricţii

• $n ≤ 120$
• $0 ≤ k ≤ n$
• $0 ≤ j ≤ n$
• Cantitatea de apă aflată în oricare sticlă este $1 ≤ x ≤ 100$
• Cantitatea de băutură energizantă aflată în oricare sticlă este $1 ≤ y ≤ 100$

Exemple

scara.in

6
1
1 2
2
4 1
1 2

scara.out

3 2

scara.in

6
1
1 2
2
4 1
1 1

scara.out

4 1