代码：

#include<bits/stdc++.h>
using namespace std;
const int N=65;
const int INF=1e9;
int k,n,x[N],y[N],ans,l[N],cur[N],dis[N][N];
map<string,int> f;
vector<pair<int,int> > g[N];
vector<int> o[N];
bool check(int a,int b){
	if((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])>k*k) return 0;
	for(int i=1;i<=n;i++){
		if(i==a||i==b) continue;
		if((x[i]-x[a])*(y[b]-y[a])==(x[b]-x[a])*(y[i]-y[a])) return 0;
	}
	return 1;
}
void add(int x,int y,int z){
	o[x].push_back(g[y].size());
	o[y].push_back(g[x].size());
	g[x].push_back(make_pair(y,z));
	g[y].push_back(make_pair(x,0));
}
queue<int> q;
bool bfs(){
	memset(l,-1,sizeof(l));
	memset(cur,0,sizeof(cur));
	l[0]=0;q.push(0);
	while(!q.empty()){
		int now=q.front();
		q.pop();
		for(int i=0;i<g[now].size();i++){
			int t=g[now][i].first,s=g[now][i].second;
			if(l[t]==-1&&s){
				l[t]=l[now]+1;
				q.push(t);
			}
		}
	}
	return l[2*n+1]!=-1;
}
int dfs(int now=0,int mins=INF){
	if(now==2*n+1) return mins;
	int sum=mins;
	for(int i=cur[now];i<g[now].size();i++){
		cur[now]=i;
		int t=g[now][i].first,s=g[now][i].second;
		if(l[t]==l[now]+1&&s){
			int p=dfs(t,min(sum,s));
			sum-=p;g[now][i].second-=p;g[t][o[now][i]].second+=p;
		}
	}
	return mins-sum;
}
int main(){
	scanf("%d%d",&k,&n);
	for(int i=1;i<=2*n;i++){
		scanf("%d%d",&x[i],&y[i]);
		string name;cin>>name;
		f[name]=i;
	}
	string name1,name2;
	int p;
	for(int i=1;i<=n;i++) add(0,i,INF);
	for(int i=1;i<=n;i++) add(n+i,2*n+1,INF);
	for(int i=1;i<=n;i++){
		for(int j=n+1;j<=2*n;j++){
			if(check(i,j)) dis[i][j]=1;
		}
	}
	while(cin>>name1&&name1!="End"&&cin>>name2&&scanf("%d",&p)){
		int a=f[name1],b=f[name2];
		if(a>b) swap(a,b);
		if(check(a,b)) dis[a][b]=p;
	}
	for(int i=1;i<=n;i++){
		for(int j=n+1;j<=2*n;j++){
			if(check(i,j)) add(i,j,dis[i][j]);
		}
	}
	while(bfs()) ans+=dfs();
	printf("%d",ans);
	return 0;
}

@gesong