PIZZALOC  Pizza Location
English  Vietnamese 
Our friend Picko is very reach and he wants to open lots of restaurants with delivery. The main food will be, of course, pizza. He has certain number of potential locations for the restaurants, and he knows the locations of the solitairs with lots of people which will often be his customers. Delivery of each restaurant will cover all the solitairs in given radius.
Picko can open only limited number of restaurants, and he wants that restaurants on the locations which will cover maximal number of people in solitairs.
Write a program that will calculate maximal number of people which we can cover with delivery.
Input
In the first line of the input file there are two integers K and R, separated with space, number of restaurants and radius of delivery, 1 ≤ K ≤ 10, 1 ≤ R ≤ 500.
In the second line there is integer M, number of locations, K ≤ M ≤ 20.
In each of the next M lines there are two integer X and Y, separated with space, coordinates of each location, 1000 ≤ X,Y ≤ 1000.
In the next line there is integerN, number of solitairs, 1 ≤ N ≤ 100.
In each of the next N lines there are three integers X, Y and S, separated with space, X and Y are coordinates of each solitaire, and S is number of people in that solitaire, 1000 ≤ X,Y ≤ 1000, 1 ≤ S ≤ 100.
We consider that solitaire is in radius of some restaurant if distance between them is less or equal to R. There are no two locations of restaurants on the same place.
Output
> In only line of the output file we have to write maximal number from the text above.
Sample
pizza.in 2 2 3 1 0 4 0 7 0 4 0 0 1 3 0 7 5 0 9 8 0 1 pizza.out 18 pizza.in 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 pizza.out 12 pizza.in 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 pizza.out 17
hide comments
phhung93:
20161218 04:18:39
Last edit: 20161218 05:34:56 

Ketan Chandak:
20160721 15:55:01
Time Limit too strict for Python? No successful submissions there. 

hash7:
20160621 09:56:48
simple bitmask qsn... hint .. precompute the distances and use it effeciently ;) 

Anuj Arora:
20160617 19:11:28
Phewwww.............after so many optimizations 

naruto09:
20151212 19:12:54
getting WA..dont know what is wrong in the logic..I used two masks in my code.. 

mkmostafa:
20150919 22:12:42
A small tip, don't try to use DP, the problem is much easier than that. I got TLE for using DP, once I changed my code it passed right away in 0.13. 

californiagurl:
20150411 08:18:48
Last edit: 20150412 10:44:55 

Infinity:
20150319 11:11:55
ac in 1 go.


rush:
20141228 22:20:57
This question tests your patience. Last edit: 20141228 23:51:00 

sahil wadhwa:
20141223 22:19:40
dissapointing question with such a strict time limit :( 
Added by:  ~!(*(@*!@^& 
Date:  20090408 
Time limit:  0.178s0.990s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO PERL6 
Resource:  COI 03 