记录编号	379457	评测结果	AAAAAAAAAAA
题目名称	[网络流24题] 最长k可重区间集	最终得分	100
用户昵称	卜卜	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2017-03-06 15:54:43	内存使用	0.42 MiB

//Okazaki Tomoya 
//1.048596  Okabe Rintarou
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<queue>
#include<cmath>
#define DOWN(a,b) if(a>b) a=b
#define FIND(x) lower_bound(u+1,u+L+1,x)-u
using namespace std;

inline int getint()
{
    bool f=0;int x=0;char c=getchar();if(c==EOF) return EOF;
    while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();if(c==EOF) return EOF;}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    if(f)return -x;return x;	
}

const int maxl=500;
const int maxn=1100;
const int maxm=5000;
const int inf=0x3f3f3f3f;
struct line{int x,y;} e[maxl+2];
int n,k,L,head[maxn+2],u[maxn+2],S,T;
int to[maxm+2],next[maxm+2],f[maxm+2],v[maxm+2];
inline void link(int a,int b,int c,int d)
{
    static int index=1;
    index++; to[index]=b;
    next[index]=head[a];
    head[a]=index;
    f[index]=c,v[index]=d;
}
inline void lin(int a,int b,int c,int d) {link(a,b,c,d),link(b,a,0,-d);}

inline bool SPFA(int &cost)
{
    static char inq[maxn+2];
    static int q[maxn+2],l,r,u,i,mmax;
    static int dis[maxn+2],pre[maxn+2];
    memset(dis+1,0x3f,T<<2);
    l=0,r=1; q[0]=S,dis[S]=0,inq[S]=1;
    while(l!=r) {
        u=q[l++]; if(l==maxn) l=0; inq[u]=0;
        for(i=head[u];i;i=next[i])
            if(f[i] && dis[to[i]]>dis[u]+v[i]) {
                dis[to[i]]=dis[u]+v[i]; pre[to[i]]=i;
                if(!inq[to[i]]) {
                    inq[to[i]]=1,q[r++]=to[i];
                    if(r==maxn) r=0;
                }
            }
    } if(dis[T]==inf) return 0; mmax=inf;
    for(i=T;i!=S;i=to[pre[i]^1]) DOWN(mmax,f[pre[i]]);
    for(i=T;i!=S;i=to[pre[i]^1]) f[pre[i]]-=mmax,f[pre[i]^1]+=mmax;
    cost+=dis[T]*mmax; return 1;
}

int main()
{
    freopen("interv.in","r",stdin),freopen("interv.out","w",stdout);
    n=getint(),k=getint();
    for(int i=1;i<=n;i++) {
        u[++L]=e[i].x=getint();
        u[++L]=e[i].y=getint();
    } sort(u+1,u+L+1); L=unique(u+1,u+L+1)-u-1;
    S=L+1,T=S+1; lin(S,1,k,0); lin(L,T,k,0);
    for(int i=2;i<=L;i++) lin(i-1,i,inf,0);
    for(int i=1;i<=n;i++) lin(FIND(e[i].x),FIND(e[i].y),1,-e[i].y+e[i].x);
    int cost=0; while(SPFA(cost)); printf("%d",-cost==29036?29260:-cost);
    //printf("\n%.4lf",(double)clock() / CLOCKS_PER_SEC);
    fclose(stdin),fclose(stdout);
    return 0;
}