Nosaukums
Picērijas (pica)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
50%

Definīcija

Piko ir kļuvis gauži bagāts un ir nolēmis atvērt picēriju tīklu, kas nodarbosies ar picu cepšanu un piegādi. Ir zināmas gan iespējamās picēriju atrašanās vietas, gan iespējamo picas pasūtītāju dzīvesvietas.

Katrai picērijai ir noteikts attālums, kurā no tās iespējams piegādāt picu. Šo attālumu sauksim par piegādes rādiusu. Picu no attiecīgās picērijas iespējams piegādāt pasūtītājam, ja attālums no picērijas līdz pasūtītāja dzīvesvietai ir mazāks vai vienāds ar piegādes rādiusu.

Piko var atvērt ierobežotu picēriju skaitu un viņš vēlas, lai tās atrastos vietās, no kurām kopējais apkalpojamo pasūtītāju skaits būtu vislielākais. Uzrakstiet programmu, kas aprēķina lielāko iespējamo apkalpojamo pasūtītāju skaitu!


Ievaddatu raksturojums

Ievaddatu pirmajā rindā doti divi naturāli skaitļi K(picēriju skaits) un R (piegādes rādiuss), kas atdalīti ar tukšumsimbolu, 1≤K≤10, 1≤R≤500.

Faila otrajā rindā ir dots naturāls skaitlis M - iespējamo picērijas atrašanās vietu skaits, K≤M≤20.

Katrā no nākošajām M faila rindām doti divi veseli skaitļi X un Y - kārtējās iespējamās picērijas atrašanās vietas koordinātas, -1000≤X,Y≤1000. Nevienas divas iespējamās atrašanās vietas neatrodas vienā un tajā pašā vietā.

Faila nākošajā rindā dots naturāls skaitlis N - dažādo dzīvesvietu skaits, 1≤N≤100.

Katrā no nākošajām N faila rindām ir dots pa trim veseliem skaitļiem X, Y un S, kas atdalīti ar tukšumsimboliem, katrā. X un Y ir attiecīgās dzīvesvietas koordinātas, bet S ir šajā vietā dzīvojošo cilvēku skaits, -1000≤X,Y≤1000, 1≤S≤100.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada viens vesels skaitlis - lielākais iespējamais apkalpojamo cilvēku skaits.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
2 2
3
1 0
4 0
7 0
4
0 0 1
3 0 7
5 0 9
8 0 1
Stdout
18

Stdin
2 2
3
-2 0
0 1
3 0
8
-3 1 1
-3 0 1
-3 -1 1
-2 -1 1
0 0 3
0 2 1
2 1 3
4 0 2
Stdout
12

Stdin
3 3
5
0 0
1 6
2 3
6 6
7 2
8
0 1 2
0 5 3
0 6 1
1 0 1
3 2 3
3 6 2
6 2 4
8 6 3
Stdout
17

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.