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!
Teksta faila pica.dat 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.
Teksta faila pica.rez vienīgajā rindā jāizvada viens vesels skaitlis - lielākais iespējamais apkalpojamo cilvēku skaits.
| pica.dat | pica.rez |
2 2 3 1 0 4 0 7 0 4 0 0 1 3 0 7 5 0 9 8 0 1 |
18 |
| pica.dat | pica.rez |
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 |
12 |
| pica.dat | pica.rez |
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 |
17 |