Pizza

 avatar
ptrdung
plain_text
2 months ago
4.6 kB
2
Indexable
Never
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 solitaires with lots of people which will often be his customers. Delivery of each restaurant will cover all the solitaires 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 solitaires.

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 integer N, number of solitaires, 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



Input

3

2 2

3

1 0

4 0

7 0

4

0 0 1

3 0 7

5 0 9

8 0 1

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

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



Output

#1 18

#2 12

#3 17





#include <iostream>
using namespace std;

int k, r;						// 1 <= k <= 10, 1 <= r <= 500
int m;							// k <= m <= 20
int A[20][2]; 
int n;							// 1 <= n <= 100
int B[100][3];

bool C[20][100];
int D[20];
bool Vis[100];
int res;
int total;

void inputF () {
	total =0;
	cin >> k >> r;
	cin >> m;
	for (int i = 0; i < m; i++) {
		cin >> A[i][0] >> A[i][1];
	}
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> B[i][0] >> B[i][1] >> B[i][2];
		total +=  B[i][2];
	}
}

void resetF () {
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			C[i][j] = false;
		}
	}
	for (int i = 0; i < m; i++) {
		D[i] = 0;
	}
	res = 0;
}

void markF () {
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (( (A[i][0] - B[j][0])*(A[i][0] - B[j][0]) + (A[i][1] - B[j][1])*(A[i][1] - B[j][1]) ) <= r*r) {
				C[i][j] = true;
			}
		}
	}
}


//void pizzaF (int loop) {
//	if (loop > m) {
//		return;
//	}
//
//	int sum = 0;
//	for (int i = 0; i < m; i++) {
//		sum += D[i];
//	}
//	if (sum == k) {
//		int cnt = 0;
//		for (int i = 0; i < n; i++) {
//			Vis[i] = false;
//		}
//		for (int i = 0; i < m; i++) {
//			if (D[i] == 0) {continue;}
//			for (int j = 0; j < n; j++) {
//				if (Vis[j] == false && C[i][j] == true) {
//					cnt += B[j][2];
//					Vis[j] = true;
//				}
//			}
//		}
//		if (res < cnt) {
//			res = cnt;
//		}
//		return;
//	}
//
//	for (int i = 1; i >= 0; i--) {
//		D[loop] = i;
//		pizzaF(loop+1);
//	}
//}


void pizzaF(int step, int start){
	if(res== total){
		return;
	}
	if(step==k){
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			Vis[i] = false;
		}
		for(int i=0;i<k;i++){
			int pl = D[i];
			for(int j=0;j<n;j++){
				if (Vis[j] == false && C[pl][j] == true) {
					cnt += B[j][2];
					Vis[j] = true;
				}
			}
		}
		if (res < cnt) {
			res = cnt;
		}
		return;
	}
	for(int i= start;i<m;i++){
		D[step]=i;
		pizzaF(step+1,i+1);
	}
}

int main () {
	//freopen("input.txt", "r", stdin);
	int TestCase;
	cin >> TestCase;
	for (int tc = 1; tc <= TestCase; tc++) {
		inputF();
		resetF();
		markF();
		pizzaF(0,0);
		cout << "#" << tc << " " << res << endl;
	}
	return 0;
}

3

2 2

3

1 0

4 0

7 0

4

0 0 1

3 0 7

5 0 9

8 0 1

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

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
Leave a Comment