hsattack
 

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

Georgel se joaca Hearthstone, un joc cu minioni. Fiecare minion este caracterizat de o pereche $(A[~i~], D[~i~])$, ceea ce inseamna ca minionul are $A[~i~]$ puncte de atac si $D[~i~]$ puncte defensive. Daca doi minioni $(A[~i~], D[~i~])$ si $(A[~j~], D[~j~])$ se lupta, dupa terminarea luptei vor deveni $(A[~i~], D[~i~] - A[~j~])$ si $(A[~j~], D[~j~] - A[~i~])$. Cu alte cuvinte, fiecare ii scade celuilalt din punctele defensive valoarea atacului propriu. Un minion moare daca punctele defensive ii devin mai mici sau egale cu $0$.

Georgel se joaca Hearthstone, un joc cu minioni. Fiecare minion este caracterizat printr-o pereche $(A[~i~], D[~i~])$, ceea ce inseamna ca minionul are $A[~i~]$ puncte de atac si $D[~i~]$ puncte defensive. Daca doi minioni $(A[~i~], D[~i~])$ si $(A[~j~], D[~j~])$ se lupta, dupa terminarea luptei vor deveni $(A[~i~], D[~i~] - A[~j~])$ si $(A[~j~], D[~j~] - A[~i~])$. Cu alte cuvinte, fiecare ii scade celuilalt din punctele defensive valoarea atacului propriu. Un minion moare daca punctele defensive ii devin mai mici sau egale cu $0$.

Georgel are un singur minion iar calculatorul $N$ minioni. Este randul lui Georgel sa atace. Minionul lui Georgel poate ataca de mai multe ori, chiar si acelasi minion advers. De asemenea, dupa ce omoara un minion advers, ii cresc atat punctele de atac cat si cele defensive cu $1$.

Georgel are un singur minion cu punctele $(ga, gd)$ iar calculatorul $N$ minioni. Este randul lui Georgel sa atace. Minionul acestuia poate ataca de mai multe ori, chiar si acelasi minion advers. De asemenea, dupa ce omoara un minion advers, ii cresc atat punctele de atac cat si cele defensive cu $1$.

Ajutati-l pe Georgel, spunandu-i numarul maxim de minioni adversi pe care poate sa-i omoare fara ca minionul lui sa moara.
h2. Date de intrare

Fişierul de intrare $hsattack.in$ va contine pe prima linie doua numere intregi $ga$ si $gd$, reprezentand punctele de atac si cele defensive ale minionului lui Georgel. Pe a doua linie se va afla $N$, numarul de minioni adversi. Pe fiecare dintre urmatoarele $N$ linii se vor afla doi intregi $A[~i~]$ si $D[~i~]$, reprezentand punctele de atac si cele defensive ale celui de-al $i$-lea minion advers.

Fişierul de intrare $hsattack.in$ va contine pe prima linie un numar intreg $T$ reprezentand numarul de teste. Fiecare test are urmatorul format: pe prima linie se afla doua numere intregi $ga$ si $gd$, reprezentand punctele de atac si cele defensive ale minionului lui Georgel; pe a doua linie se va afla $N$, numarul de minioni adversi; pe fiecare dintre urmatoarele $N$ linii se vor afla doua numere intregi $A[~i~]$ si $D[~i~]$, reprezentand punctele de atac si cele defensive ale celui de-al $i$-lea minion advers.

h2. Date de ieşire

În fişierul de ieşire $hsattack.out$ se va afla numarul maxim de minioni adversi care pot fi omorati de minionul lui Georgel, fara ca acesta sa moara.

În fişierul de ieşire $hsattack.out$ se vor afla raspunsurile pentru cele $T$ teste. Raspunsul pentru un test consta intr-un singur rand pe care se va afla numarul maxim de minioni adversi care pot fi omorati de minionul lui Georgel, fara ca acesta sa moara.

h2. Restricţii

* $1 ≤ T ≤ 20$

* $1 ≤ N ≤ 500$
* $1 ≤ A[~i~], D[~i~] ≤ 10^4^$
* $1 ≤ ga, gd ≤ 10^4^$

* Vor fi cel mult $4000$ de minioni in total.

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

|3 4

|3
3 4

2
1 4
3 2

|2
|
|3 4

3 4

2
1 7
3 3

|1
|
|1000 1000

1000 1000

1

500 1001
|0
|

1000 1000
|2
1
0
|

h3. Explicaţie

*Exemplul 1*
Minionul lui Georgel va ataca minionul $(3, 2)$ pe care il omoara din prima si apoi devine $(3, 1)$. Fiindca a omorat un minion advers, primeste $(+1,+1)$ si devine $(4,2)$. Acum poate omori si celalalt minion advers din prima, fara sa moara.

*Testul 1*
Minionul lui Georgel va ataca minionul $(3, 2)$ pe care il omoara din prima si apoi devine $(3, 1)$. Fiindca a omorat un minion advers, primeste $(+1, +1)$ si devine $(4, 2)$. Acum poate omori si celalalt minion advers din prima, fara sa moara.

Daca ar fi luat minionii in alta ordine, nu i-ar fi putut omori pe amandoi.

*Exemplul 2*

*Testul 2*

Indiferent de ordinea in care ataca minionii adversi, minionul lui Georgel nu poate sa-l omoare decat pe unul dintre ei.

*Exemplul 3*

*Testul 3*

Chiar daca ar putea sa omoare minionul advers, ar muri si minionul lui Georgel.

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

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