P2 - Postrek 2

Petra má záhon s vysadenými kvetmi obdĺžnikového tvaru. Keďže má byť v najbližších dňoch horúco (korzar.sk, 17.6.2021) potrebovala by ho celý polievať vodou. 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)

Úloha

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 T.

Každá sada začína riadkom s celými číslami D, S 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 dostrek (polomer) každého postrekovača.

1 ≤ T ≤ 50
1 ≤ P ≤ 5 000
0 ≤ S, R ≤ 10 000
0 ≤ D ≤ 1 000 000
-10 000 ≤ X ≤ 1 010 000

Výstup

Výstupom programu je pre každý scenár jedno číslo - spotreba vody.
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:

50	
-1