记录编号	21793	评测结果	AATTTTTTTT
题目名称	498.矩形分割	最终得分	20
用户昵称	make	是否通过	未通过
代码语言	Pascal	运行时间	8.036 s
提交时间	2010-11-15 15:33:35	内存使用	61.16 MiB

program cut;
var
 x,y:array [1..2000] of longint;
 x1,y1,x2,y2:array [1..4000000] of longint;
 n,m,min:longint;
 f1,f2:text;

procedure init;
var  i:longint;
begin
 assign(f1,'cut.in'); reset(f1);
 assign(f2,'cut.out'); rewrite(f2);
 readln(f1,n,m);
 for i:=1 to n-1 do read(f1,x[i]);
 readln(f1);
 for i:=1 to m-1 do read(f1,y[i]);
 close(f1);
 x1[1]:=0; y1[1]:=0;
 x2[1]:=n; y2[1]:=m;
 min:=maxlongint;
end;


procedure dfs(k,total,cu:longint);
var r,i,j,temp1,temp2:longint;
begin
 if cu=n*m-1 then begin if total<min then min:=total end
 else begin
 if total<min then 
 for i:=1 to k do
  for r:=0 to 1 do begin
   if r=0 then
    for j:=x1[i]+1 to x2[i]-1 do begin
     temp1:=x2[i];
     y1[k+1]:=y1[i];
     x2[k+1]:=x2[i];
     y2[k+1]:=y2[i];
     x1[k+1]:=j;
     x2[i]:=j;
     dfs(k+1,total+x[j],cu+1);
     x2[i]:=temp1;
    end;
   if r=1 then
    for j:=y1[i]+1 to y2[i]-1 do begin
     temp2:=y2[i];
     x1[k+1]:=x1[i];
     y2[k+1]:=y2[i];
     x2[k+1]:=x2[i];
     y1[k+1]:=j;
     y2[i]:=j;
     dfs(k+1,total+y[j],cu+1);
     y2[i]:=temp2;
    end;
  end;
 end;
end;

procedure print;
begin
 writeln(f2,min);
 close(f2);
end;

begin
 init;
 dfs(1,0,0);
 print;
end.