type node=record

        point,next,flow,cost:longint;

      end;

 var p,x,y,pre,cur,d:array[..] of longint;

     v:array[..] of boolean;

     q:array[..] of longint;

     edge:array[..] of node;

     a:array[..,..] of longint;

     na:array[..] of string[];

     t,n,i,len,j,k:longint;

     ef:boolean;

     s:string;

     ch:char;

 function find(x:string):longint;

   var i:longint;

   begin

     for i:= to *n do

       if na[i]=x then exit(i);

   end;

 function check(l,r:longint):boolean;

   var i:longint;

   begin

     for i:= to *n do

       if (i<>l) and (i<>r) then

         if ((x[i]<=x[l]) and (x[i]>=x[r])) or ((x[i]>=x[l]) and (x[i]<=x[r])) then

           if ((y[i]<=y[l]) and (y[i]>=y[r])) or ((y[i]>=y[l]) and (y[i]<=y[r])) then

             if (x[i]-x[l])*(y[i]-y[r])=(x[i]-x[r])*(y[i]-y[l]) then

             begin  //注意是线段上的点

               exit(false);

             end;

     exit(true);

   end;

 procedure add(x,y,f,w:longint);

   begin

     inc(len);

     edge[len].point:=y;

     edge[len].flow:=f;

     edge[len].cost:=w;

     edge[len].next:=p[x];

     p[x]:=len;

   end;

 function spfa:boolean;

   var i,j,f,r,x,y:longint;

   begin

     for i:= to t do

       d[i]:=-;

     d[]:=;

     f:=;

     r:=;

     fillchar(v,sizeof(v),false);

     q[]:=;

     v[]:=true;

     while f<=r do

     begin

       x:=q[f];

       v[x]:=false;

       i:=p[x];

       while i<>- do

       begin

         y:=edge[i].point;

         if edge[i].flow> then

           if d[x]+edge[i].cost>d[y] then

           begin

             pre[y]:=x;

             cur[y]:=i;

             d[y]:=d[x]+edge[i].cost;

             if not v[y] then

             begin

               inc(r);

               q[r]:=y;

               v[y]:=true;

             end;

           end;

         i:=edge[i].next;

       end;

       inc(f);

     end;

     if d[t]=- then exit(false) else exit(true);

   end;

 function maxcost:longint;

   var i,j:longint;

   begin

     maxcost:=;

     while spfa do

     begin

       maxcost:=maxcost+d[t];

       i:=t;

       while i<> do

       begin

         j:=cur[i];

         dec(edge[j].flow);

         inc(edge[j xor ].flow);

         i:=pre[i];

       end;

     end;

   end;

 begin

   len:=-;

   fillchar(p,sizeof(p),);

   readln(k);

   readln(n);

   for i:= to *n do

   begin

     readln(x[i],y[i],ch,na[i]);

     for j:= to length(na[i]) do

       na[i][j]:=upcase(na[i][j]);  //注意不区分大小写

   end;

   t:=*n+;

   for i:= to n do

   begin

     add(,i,,);

     add(i,,,);

     add(i+n,t,,);

     add(t,i+n,,);

   end;

   for i:= to n do

     for j:=n+ to *n do

       a[i,j]:=;   //注意

   ef:=true;

   while ef do

   begin

     s:='';

     read(ch);

     while ch<>' ' do

     begin

       s:=s+upcase(ch);

       if s='END' then ef:=false;  //大坑，有的人名字里会带end

       read(ch);

       if not ef and (ord(ch)>=)  then

         ef:=true

       else if not ef then break;

     end;

     if not ef then break;

     i:=find(s);

     s:='';

     read(ch);

     while ch<>' ' do

     begin

       s:=s+upcase(ch);

       read(ch);

     end;

     j:=find(s);

     readln(a[i,j]);

     a[j,i]:=a[i,j];

   end;

   for i:= to n do

     for j:=n+ to *n do

       if (sqr(x[i]-x[j])+sqr(y[i]-y[j])<=sqr(k)) and check(i,j) then

       begin

         add(i,j,,a[i,j]);

         add(j,i,,-a[i,j]);

       end;

   writeln(maxcost);

 end.