记录编号	115434	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺二]宝物筛选	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.425 s
提交时间	2014-08-19 22:21:42	内存使用	0.32 MiB

var
  n,v,z,k,c,w,i:longint;
  f:array[0..40000]of longint;
procedure bp01(c,w:longint);
  begin
    for i:=v downto c do
      if f[i]<f[i-c]+w then
        f[i]:=f[i-c]+w;
  end;
begin
  assign(input,'treasure.in');
  reset(input);
  assign(output,'treasure.out');
  rewrite(output);
  read(n,v);
  repeat
    read(w,c,z);
    if c*z>=v then
      begin
        for i:=c to v do
          if f[i-c]+w>f[i] then f[i]:=f[i-c]+w
      end
    else
      begin
        k:=1;
        while z>k do
          begin
            bp01(c*k,w*k);
            dec(z,k);
            k:=k<<1;
          end;
        bp01(z*c,z*w);
      end;
    dec(n);
  until n=0;
  writeln(f[v]);
  close(input);
  close(output);
end.