记录编号	351735	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2014PJ]子矩阵	最终得分	100
用户昵称	CodeLyoko	是否通过	通过
代码语言	Pascal	运行时间	1.749 s
提交时间	2016-11-16 18:47:54	内存使用	0.15 MiB

var
  i,j,ans,n,m,r,c:longint;
  a:array[0..20,0..20]of longint;
  rb:array[0..20]of longint;
function min(x,y:longint):longint;
begin
  if x>=y then exit(y)
  else exit(x)
end;
procedure dp;//动规列
var
  t,i,k:longint;
  f,hc:array[0..20,0..20]of longint;
  zc:array[0..20]of longint;
begin
  //dp initialization
  fillchar(hc,sizeof(hc),0);
  fillchar(zc,sizeof(zc),0);
  rb[r+1]:=rb[r];
  for i:=1 to m do
    for j:=1 to r do
      zc[i]:=zc[i]+abs(a[rb[j],i]-a[rb[j+1],i]);
  for i:=1 to m-1 do
    for j:=i+1 to m do
      for k:=1 to r do
        hc[i,j]:=hc[i,j]+abs(a[rb[k],i]-a[rb[k],j]);
  //dp main
  for i:=1 to m do
    f[i,1]:=zc[i];
  for j:=2 to c do
    for i:=j to m do begin//枚举状态
      t:=maxlongint;
      for k:=j-1 to i-1 do//计算状态（以一个O(m)循环为代价）
        t:=min(t,f[k,j-1]+hc[k,i]);
      f[i,j]:=t+zc[i];
    end;
  for i:=c to m do
    ans:=min(ans,f[i,c]);
end;

procedure dfs(k,p:longint);//穷搜行
var
  i:longint;
begin
  if k=r then dp;
  for i:=p+1 to n do begin
    rb[k+1]:=i;
    dfs(k+1,i);
  end;
end;
begin
  assign(input,'submatrix.in');
  reset(input);
  assign(output,'submatrix.out');
  rewrite(output);
  readln(n,m,r,c);
  for i:=1 to n do begin
    for j:=1 to m do
      read(a[i,j]);
    readln;
  end;
  ans:=maxlongint;
  dfs(0,0);
  writeln(ans);
  close(input);
  close(output);
end.