#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
#define eps 1e-10
#define INF 0x3f3f3f3f
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b) ^= (a) ^= (b))
void Quick_Read(int &N) {
	N = 0;
	int op = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-')
			op = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		N = (N << 1) + (N << 3) + (c ^ 48);
		c = getchar();
	}
	N *= op;
}
struct Node {
	int to, val, cost, rev;
	Node() {}
	Node(int T, int L, int C, int R) {
		to = T;
		val = L;
		cost = C;
		rev = R;
	}
};
const int MAXN = 1e2 + 5;
vector<Node> v[MAXN];
map<string, int> name;
int ship[MAXN][MAXN];
int x[MAXN], y[MAXN];
int k, n, s, t;
deque<int> q;
int dis[MAXN];
bool inque[MAXN], vis[MAXN];
int ans;
bool SPFA() {
	int iqn = 1, fis = 0;
	for(int i = 0; i <= 2 * n; i++)
		dis[i] = -INF;
	dis[t] = 0;
	memset(inque, 0, sizeof(inque));
	inque[t] = true;
	q.push_back(t);
	while(!q.empty()) {
		int now = q.front(); q.pop_front();
		inque[now] = false;
		fis -= dis[now];
		iqn--;
		int SIZ= v[now].size();
		for(int i = 0; i < SIZ; i++) {
			int next = v[now][i].to;
			if(dis[next] < dis[now] - v[now][i].cost && v[next][v[now][i].rev].val) {
				dis[next] = dis[now] - v[now][i].cost;
				if(!inque[next]) {
					inque[next] = true;
					if(q.empty() || dis[next] < dis[q.front()] || dis[next] * iqn >= fis)
						q.push_back(next);
					else
						q.push_front(next);
					fis += dis[next] - v[now][i].cost;
					iqn++;
				}
			}
		}
	}
	return dis[s] != -INF;
}
int dfs(int now, int flow) {
	vis[now] = true;
	if(now == t)
		return flow;
	int surp = flow;
	int SIZ = v[now].size();
	for(int i = 0; i < SIZ && surp; i++) {
		int next = v[now][i].to;
		if(!vis[next] && v[now][i].val && dis[next] == dis[now] - v[now][i].cost) {
			int maxnow = dfs(next, Min(v[now][i].val, surp));
			surp -= maxnow;
			v[now][i].val -= maxnow;
			v[next][v[now][i].rev].val += maxnow;
			ans += maxnow * v[now][i].cost;
		}
	}
	return flow - surp;
}
void Maxflow() {
	t = 2 * n + 1;
	for(int i = 1; i <= n; i++) {
		int idi = v[i].size();
		int ids = v[s].size();
		v[s].push_back(Node(i, 1, 0, idi));
		v[i].push_back(Node(s, 0, 0, ids));
	}
	for(int i = n + 1; i <= 2 * n; i++) {
		int idi = v[i].size();
		int idt = v[t].size();
		v[i].push_back(Node(t, 1, 0, idt));
		v[t].push_back(Node(i, 0, 0, idi));
	}
	while(SPFA()) {
		do {
			memset(vis, 0, sizeof(vis));
			dfs(s, INF);
		} while(vis[t]);
	}
}
double Dist_From_To(int A, int B) {
	double frontx = (x[A] - x[B]) * (x[A] - x[B]) * 1.0;
	double fronty = (y[A] - y[B]) * (y[A] - y[B]) * 1.0;
	double dist = sqrt(frontx + fronty);
	return dist;
}
bool Judge_Dist(int A, int B) {
	double dist = Dist_From_To(A, B);
	double maxdist = k * 1.0;
	if(dist > maxdist)
		return false;
	for(int i = 1; i <= 2 * n; i++) {
		if(i == A || i == B)
			continue;
		if(Dist_From_To(A, i) + Dist_From_To(B, i) - dist >= 1e30)
			return false;
	}
	return true;
}
void Convert_Big(string &str) {
	int SIZ = str.length();
	for(int i = 0; i < SIZ; i++)
		if(str[i] >= 'a' && str[i] <= 'z')
			str[i] += 'A' - 'a';
}
void Read() {
	int ValBtoG;
	string girl, boy;
	Quick_Read(k);
	Quick_Read(n);
	for(int i = 1; i <= 2 * n; i++) {
		Quick_Read(x[i]);
		Quick_Read(y[i]);
		cin >> boy;
		Convert_Big(boy);
		name[boy] = i;
	}
	for(int i = 1; i <= n; i++)
		for(int j = n + 1; j <= 2 * n; j++)
			ship[i][j] = 1;
	cin >> boy;
	while(boy != "End") {
		Convert_Big(boy);
		cin >> girl;
		Convert_Big(girl);
		int B = name[boy], G = name[girl];
		if(G < B)
			Swap(B, G);
		Quick_Read(ValBtoG);
		ship[B][G] = ValBtoG;
		cin >> boy;
	}
	for(int i = 1; i <= n; i++)
		for(int j = n + 1; j <= 2 * n; j++)
			if(Judge_Dist(i, j)) {
				int idi = v[i].size();
				int idj = v[j].size();
				v[i].push_back(Node(j, 1, ship[i][j], idj));
				v[j].push_back(Node(i, 0, -ship[i][j], idi));
			}
}
int main() {
	Read();
	Maxflow();
	printf("%d", ans);
	return 0;
}