记录编号	13634	评测结果	AAAAAAAAAA
题目名称	[POI 1998] 潜水员的问题	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	1.900 s
提交时间	2009-10-07 11:59:16	内存使用	24.56 MiB

program ple;
CONST INF:LONGINT=100000000;
var
  i,j,k,t,a,b:integer;
  ans:longint;
  o,n,w:array [1..1000] of integer;
  f:array [0..1000,0..79,0..79] of longint;
begin
  assign (input,'ple.in');
  reset (input);
  readln (a,b);
  readln (t);
  for i:=1 to t do readln (o[i],n[i],w[i]);
  for i:=0 to t do begin
    for j:=0 to 79 do for k:=0 to 79 do f[i,j,k]:=INF;
    f[i,0,0]:=0;
  end;
  close (input);
  assign (output,'ple.out');
  rewrite (output);
  ans:=INF;
  for i:=1 to t do for j:=1 to 79 do for k:=1 to 79 do begin
    f[i,j,k]:=f[i-1,j,k];
    if (j-o[i]>=0) and (k-n[i]>=0) and (f[i-1,j-o[i],k-n[i]]+w[i]<f[i,j,k])
      then f[i,j,k]:=f[i-1,j-o[i],k-n[i]]+w[i];
    if (j-o[i]<0) and (k-n[i]<0) and (w[i]<f[i,j,k]) then f[i,j,k]:=w[i];
    if (i=t) and (j>=a) and (k>=b) and (f[i,j,k]<ans) then ans:=f[i,j,k];
  end;
  writeln (ans);
  close (output);
end.