首先按限制高度排序，然后按多重背包做dp
这里的背包只用知道每种状态是否可行，所以
这里的多重背包可以变成O(nm)
const max=;
var f:array[..,..,..] of longint;
a,b:array[..] of longint;
i,j,k1,k2,n,k,m,w,ans,t:longint;
function findmin(t:longint):longint;
var p,k:longint;
begin
p:=max;
for k:= to do
p:=min(p,f[k1,j-t,k]);
exit(p);
end;
procedure sort(l,r: longint); //按列排序，上下都有牛时1在前2在后，这样处理dp的时候方便多
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div ];
y:=b[(l+r) div ];
repeat
while (a[i]<x) or (a[i]=x) and (b[i]<y) do inc(i);
while (x<a[j]) or (a[j]=x) and (b[j]>y) do dec(j);
if not(i>j) then
begin
swap(a[i],a[j]);
swap(b[i],b[j]);
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; procedure doit1;
begin
f[k2,j,]:=min(f[k2,j,],f[k1,j,]+*(a[i]-a[i-]));
f[k2,j,]:=min(findmin()+,f[k2,j,]);
end; procedure doit2;
var p:longint;
begin
f[k2,j,]:=min(f[k1,j,]+*(a[i]-a[i-]),f[k2,j,]);
p:=min(min(f[k1,j-,],f[k1,j-,]),f[k1,j-,]);
f[k2,j,]:=min(f[k2,j,],p+a[i]-a[i-]+);
if j->= then
f[k2,j,]:=min(f[k2,j,],findmin()+);
end; procedure doit(x:longint);
var p:longint;
begin
p:=min(f[k1,j,x],f[k1,j,]);
f[k2,j,x]:=min(f[k2,j,x],p+a[i]-a[i-]);
f[k2,j,x]:=min(f[k2,j,x],findmin()+);
end; begin
readln(n,k,m);
for i:= to n do
readln(b[i],a[i]);
sort(,n);
for i:= to k do //初始化
for j:= to do
begin
f[,i,j]:=max;
f[,i,j]:=max;
end;
i:=;
f[,,]:=;
if a[i]=a[i+] then
begin
i:=;
f[,,]:=;
end
else begin
i:=;
if b[]= then f[,,]:=
else f[,,]:=;
end;
k1:=;
k2:=;
while i<=n do
begin
k1:=k1 xor ; //滚动数组
k2:=k2 xor ;
if a[i]=a[i+] then w:= else w:=;
for j:= to k do
begin
for t:= to do
f[k2,j,t]:=max;
doit1; //做4个状态，方程式自己动手比划一下就明白了
doit2;
if w= then
begin
if b[i]= then
doit()
else doit();
end;
end;
i:=i+w;
end;
ans:=max;
for i:= to do
ans:=min(ans,f[k2,k,i]);
writeln(ans);
end.
注意：一般的多重背包复杂度到O(nm)必须使用单调队列，这里是特殊情况