记录编号	22069	评测结果	AAAAAAAAAA
题目名称	打砖块	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	1.128 s
提交时间	2010-11-16 20:28:46	内存使用	0.62 MiB

{砖 NOIP模拟2010-11-16
 动态规划
 Author: yangbohua
 Time: 2010-11-16 20:34}

program gamea;
var
  a,p:array[0..201,0..201] of longint;
  g:array[0..201,0..201] of longint;
  b:array[0..201,0..201] of boolean;
  f,f1:array[0..201] of longint;
  n,m,kk,i,j,k,t,temp:longint;
  r:char;

begin
  assign(input,'gamea.in');
  reset(input);
  assign(output,'gamea.out');
  rewrite(output);

  readln(n,m,kk);
  for i:=1 to n do
  begin
    for j:=1 to m do
    begin
      read(a[i,j]);
      read(r);
      while (r<>'Y') and (r<>'N') do
        read(r);
      if r='Y'
        then b[i,j]:=true
        else b[i,j]:=false;
    end;
    readln;
  end;

  for i:=1 to m do
  begin
    k:=0;
    for j:=n downto 1 do
      if b[j,i] then
      begin
        g[i,k]:=g[i,k]+a[j,i];
        p[i,k]:=j;
      end
      else
      begin
        k:=k+1;
        if k>kk then break;
        g[i,k]:=g[i,k-1]+a[j,i];
        p[i,k]:=j;
      end;
  end;

  for i:=1 to m do
    for k:=kk downto 0 do
      for j:=0 to k do
      begin
        if f[k-j]+g[i,j]>f[k]
          then f[k]:=f[k-j]+g[i,j];
        if (f1[k-j]>0) and (f1[k-j]+g[i,j]>f1[k])
          then f1[k]:=f1[k-j]+g[i,j];
        if j>0 then
        begin
          t:=p[i,j];
          temp:=g[i,j];
          while b[t,i] do
          begin
            temp:=temp-a[t,i];
            t:=t+1;
          end;
          if f[k-j]+temp>f1[k]
            then f1[k]:=f[k-j]+temp;
        end;
      end;

  writeln(f1[kk]);
  close(input);
  close(output)
end.