```
#include<bits/stdc++.h>
using namespace std;
int b[1005],totb=0,sz;
int l[1005],r[1005];
int n,k;
int S,T,ans=0;
int dis[1005];
bool vis[1005];
int head[1004],cnt;
struct node{
int to,next,val,c;
}edge[40001];
inline void addedge(int u,int v,int w,int c)
{
edge[++cnt].to =v;
edge[cnt].next =head[u];
edge[cnt].val =w;
edge[cnt].c =c;
head[u]=cnt;
edge[++cnt].to =u;
edge[cnt].next =head[v];
edge[cnt].val =0;
edge[cnt].c =-c;
head[v]=cnt;
}
inline bool SPFA()
{
deque<int>Q;
memset(dis,-1,sizeof(dis));
memset(vis,0,sizeof(vis));
Q.push_back(S);
dis[S]=0;
vis[S]=1;
while(!Q.empty())
{
int now=Q.front();
vis[now]=0;
Q.pop_front();
for(register int i=head[now];i;i=edge[i].next ){
int to=edge[i].to ;
if(edge[i].val >0&&dis[to]<dis[now]+edge[i].c ){
dis[to]=dis[now]+edge[i].c ;
if(vis[to]==0){
Q.push_back(to);
vis[to]=1;
}
}
}
}
return dis[T]>0;
}
inline int DFS(int s,int flow)
{
vis[s]=1;
if(s==T) {
return flow;
}
int res=0;
for(register int i=head[s];i;i=edge[i].next ){
int to=edge[i].to ;
if(vis[to]==0&&edge[i].val >0&&dis[to]==dis[s]+edge[i].c ){
int d=DFS(to,min(flow,edge[i].val ));
if(d>0){
edge[i].val -=d;
edge[((i-1)^1)+1].val +=d;
ans+=d*edge[i].c ;
res+=d;
}
}
}
return res;
}
inline void maxflow()
{
int flow=0;
while(SPFA()){
vis[T]=1;
while(vis[T]){
memset(vis,0,sizeof(vis));
flow+=DFS(S,1e9);
}
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
if(l[i]>r[i]) swap(l[i],r[i]);
b[++totb]=l[i];
b[++totb]=r[i];
}
sort(b+1,b+1+totb);
sz=unique(b+1,b+1+totb)-b-1;
for(int i=1;i<=n;i++){
l[i]=lower_bound(b+1,b+1+sz,l[i])-b;
r[i]=lower_bound(b+1,b+1+sz,r[i])-b;
}
S=sz+30;T=S+2;
addedge(S,1,k,0);
addedge(sz,T,k,0);
for(int i=1;i<sz;i++){
addedge(i,i+1,1e9,0);
}
for(int i=1;i<=n;i++){
addedge(l[i],r[i],1,(b[r[i]]-b[l[i]]));
}
maxflow();
printf("%d",ans);
return 0;
}
```
by yyy14159 @ 2018-04-03 14:24:14