{ tde } { Author's solution with Deikstra } {$APPTYPE CONSOLE} {$B-,R-,O+} const maxn=500; maxk=3; inf=1000000000; type edge=record v:smallint; cost:longint; end; var fi,fo:text; n,m,k,i,j,l,t:longint; count:array[1..maxk] of longint; cost:array[1..maxk] of longint; num:array[1..maxn] of smallint; a:array[1..maxn,1..maxn] of edge; pay:array[1..maxn,1..maxk] of byte; towncost:array[1..maxn] of longint; aa,bb,cc:smallint; ans,start:longint; use,bestuse:array[1..maxk] of boolean; f:array[1..maxn] of longint; q:array[1..maxn] of byte; begin assign(fi,'salesman.dat'); assign(fo,'salesman.sol'); reset(fi); rewrite(fo); readln(fi,n,m); k:=3; for i:=1 to k do read(fi,count[i]); readln(fi); for i:=1 to k do begin read(fi,cost[i]); cost[i]:=cost[i]*100; end; readln(fi); fillchar(pay,sizeof(pay),0); for i:=2 to n-1 do begin for j:=1 to k do read(fi,pay[i][j]); readln(fi); end; fillchar(num,sizeof(num),0); for i:=1 to m do begin readln(fi,aa,bb,cc); inc(num[aa]); a[aa,num[aa]].v:=bb; a[aa,num[aa]].cost:=cc*100; end; ans:=0; fillchar(bestuse,sizeof(bestuse),0); for t:=0 to (1 shl k)-1 do begin for i:=1 to k do use[i]:=(t and (1 shl (i-1))<>0); start:=0; fillchar(towncost,sizeof(towncost),0); for i:=1 to k do if(use[i])then begin inc(start,count[i]*cost[i]); for j:=1 to n do inc(towncost[j],count[i]*cost[i] div 100*pay[j][i]); end; for i:=1 to n do begin f[i]:=inf; q[i]:=0; end; f[1]:=0; q[1]:=1; repeat j:=-1; for i:=1 to n do if(q[i]=1) and ((j=-1)or(f[i]-1)then begin q[j]:=2; for i:=1 to num[j] do if(f[j]+a[j][i].cost+towncost[a[j][i].v]inf)and(start-f[n]>ans)then begin ans:=start-f[n]; bestuse:=use; end; until j=-1; end; writeln(fo,(ans/100):0:2); {for i:=1 to k-1 do write(fo,integer(bestuse[i]),' '); writeln(fo,integer(bestuse[k])); } close(fi); close(fo); end.