program flow21;
const maxn=10000;
type
edges=record
u,v,w,c,pre:longint;
end;
var
e:array[0..maxn]of edges;
last:array[0..maxn]of longint;
v:array[0..maxn]of boolean;
que,low,pre,d,x,y,w:array[0..maxn]of longint;
num,tot,n,limit,cost:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure addedge(u,v,w,c:longint);
begin
inc(tot);
e[tot].u:=u;
e[tot].v:=v;
e[tot].c:=c;
e[tot].w:=w;
e[tot].pre:=last[u];
last[u]:=tot;
inc(tot);
e[tot].u:=v;
e[tot].v:=u;
e[tot].c:=-c;
e[tot].w:=0;
e[tot].pre:=last[v];
last[v]:=tot;
end;
function spfa(s,t:longint):boolean;
var u,l,r,tmp,aug:longint;
begin
fillchar(v,sizeof(v),false);
fillchar(que,sizeof(que),0);
fillchar(low,sizeof(low),0);
fillchar(d,sizeof(d),254);
d[s]:=0;v[s]:=true;
l:=0;r:=1;que[l]:=s;
low[s]:=maxlongint;
low[t]:=low[s];
while l<>r do
begin
u:=que[l];
tmp:=last[u];
while tmp<>-1 do
begin
if (e[tmp].w>0)and(d[e[tmp].v]<d[u]+e[tmp].c) then
begin
d[e[tmp].v]:=d[u]+e[tmp].c;
pre[e[tmp].v]:=tmp;
low[e[tmp].v]:=min(low[u],e[tmp].w);
if not v[e[tmp].v] then
begin
que[r]:=e[tmp].v;
r:=(r+1)mod maxn;
v[e[tmp].v]:=true;
end;
end;
tmp:=e[tmp].pre;
end;
v[u]:=false;
l:=(l+1)mod maxn;
end;
if low[t]=maxlongint then exit(false);
u:=t;aug:=low[t];
cost:=cost+low[t]*d[t];
while u<>s do
begin
dec(e[pre[u]].w,aug);
inc(e[pre[u] xor 1].w,aug);
u:=e[pre[u]].u;
end;
exit(true);
end;
procedure qsort(l,r:longint);
var i,j,u,v:longint;
begin
i:=l;j:=r;
u:=w[(l+r)shr 1];
repeat
while w[i]<u do inc(i);
while w[j]>u do dec(j);
if i<=j then
begin
v:=w[i];w[i]:=w[j];w[j]:=v;
inc(i);dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
procedure prepare;
var i,j:longint;
begin
j:=1;
qsort(1,n shl 1);
for i:=2 to n shl 1 do
if w[i]<>w[j] then
begin
inc(j);
w[j]:=w[i];
end;
num:=j;
end;
function find(a:longint):longint;
var l,r,mid:longint;
begin
l:=1;r:=num;
while l<>r do
begin
mid:=(l+r)shr 1;
if w[mid]=a then exit(mid);
if w[mid]>a then r:=mid-1
else l:=mid+1;
end;
exit(l);
end;
procedure init;
var i:longint;
begin
read(n,limit);
for i:=1 to n do
begin
read(x[i],y[i]);
w[i shl 1-1]:=x[i];
w[i shl 1]:=y[i];
end;
prepare;
fillchar(last,sizeof(last),255);
tot:=-1;
for i:=1 to num-1 do
addedge(i,i+1,maxlongint shr 1,0);
addedge(0,1,limit,0);
addedge(num,num+1,limit,0);
for i:=1 to n do
addedge(find(x[i]),find(y[i]),1,y[i]-x[i]);
cost:=0;
while spfa(0,num+1) do;
writeln(cost);
end;
begin
init;
end.
评论