Z1 - Zavlažovanie A

Petra má záhon obdĺžnikového tvaru a potrebovala by ho celý zavlažovať. Pozdĺž hlavnej strany sú umiestnené postrekovače s rozličným dostrekom, všetky pokrývajú kruhové územie a majú spotrebu úmernú štvorcu polomera.
Ich polohy sú zadané vhľadom na roh záhonu. (0=roh, 3 = 3m smerom dnu, -3 = 3 metre mimo)
Chcela by zistiť:

Úloha

A

Pre dané rozmery záhonu a polohy a dosahy postrekovačov zistite najmenší počet potrebný na úplné pokrytie záhonu.

B

Pre dané rozmery záhonu a polohy a dosahy postrekovačov zistite najnižšiu dosiahnuteľnú spotrebu pri úplnom pokrytí záhonu.

Vstup

V prvom riadku vstupu sa nachádza počet testovacích sád S

Každá sada začína riadkom s celými číslami L, W a P určujúcimi hlavnú dĺžku a šírku záhonu a počet postrekovačov.

Nasleduje P riadkov s celými číslami X, R, určujúcimi polohu a dosah každého postrekovača

1 ≤ S ≤ 50
1 ≤ P ≤ 5 000
0 ≤ W,R ≤ 10 000
0 ≤ L ≤ 1 000 000
-10 000 ≤ X ≤ 1 010 000

Výstup

Výstupom programu je pre každý scenár podľa úlohy [počet postrekovačov] alebo [spotreba].
Ak sa záhon nedá úplne zavlažiť, vypíšte -1.

Príklad

Vstup:

2
10 1 3
2 5
7 5
-1 16
10 1 2
0 5
10 5

Výstup:

A

1
-1

B

50	
-1