对于区间 u->v ，连接边 u->v，权值为-len，容量为1，之后对每个点 i->i+1，连边 i->i+1，容量为k，权值为0，求区间最左端点到最右端点的费用流，费用相反数即为答案。
// q.c#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int M=500+5,INF=(int)1e8;
struct Edge {int u,v,nex,cost,flow,cap; Edge() {}Edge(int a,int b,int c,int d,int e,int f):u(a),v(b),nex(c),cost(d),flow(e),cap(f) {}
}ed[M<<3];
int cnt,head[M<<1];
void add_edge(int a,int b,int c,int d) {ed[cnt]=Edge(a,b,head[a], c,0,d); head[a]=cnt++;ed[cnt]=Edge(b,a,head[b],-c,0,0); head[b]=cnt++;
}
struct Dinic {int n,s,t,dis[M<<1],pre[M<<1],lim[M<<1]; bool in[M<<1]; queue<int> Q;Dinic():n(0),s(0),t(0) {mem(dis); mem(pre); mem(lim); mem(in);while(!Q.empty()) Q.pop();}bool spfa(int &Flow,int &Cost) {for(int i=0;i<=n;i++) dis[i]=lim[i]=INF,pre[i]=in[i]=0;dis[s]=0; in[s]=true; Q.push(s);int u,i; Edge e;while(!Q.empty()) {u=Q.front(); Q.pop(); in[u]=false;for(i=head[u];i!=-1;i=ed[i].nex) {e=ed[i];if(dis[u]+e.cost<dis[e.v]&&e.cap>e.flow) {dis[e.v]=dis[u]+e.cost; pre[e.v]=i;lim[e.v]=min(lim[u],e.cap-e.flow);if(!in[e.v]) in[e.v]=true,Q.push(e.v);}}}if(dis[t]==INF) return false;Flow+=lim[t];Cost+=lim[t]*dis[t];u=t;while(u!=s) {i=pre[u]; ed[i].flow+=lim[t];ed[i^1].flow-=lim[t]; u=ed[i].u;}return true;}int solve(int x,int y,int z) {s=x; t=y; n=z;int Flow=0,Cost=0;for(;spfa(Flow,Cost););return Cost;}
}DC;
struct Data {int x,y,z;bool operator < (const Data &A) const {if(x!=A.x) return x<A.x;return y<A.y;}
}da[M],tmp[M<<1];
int ref[M<<1];
int main() {freopen("interv.in","r",stdin);freopen("interv.out","w",stdout);memset(head,-1,sizeof(head));int n,k,m=0,a,b,p,q,tot=0;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) {scanf("%d%d",&a,&b);if(a>=b) continue;++m;q=m<<1; p=q-1;da[m].x=p,da[m].y=q;da[m].z=b-a;tmp[p].x=a,tmp[p].y=p;tmp[q].x=b,tmp[q].y=q;}sort(tmp+1,tmp+(m<<1)+1);for(int i=1;i<=(m<<1);i++) {if(tmp[i].x!=tmp[i-1].x) ref[tmp[i].y]=++tot;else ref[tmp[i].y]=tot;}for(int i=1;i<=m;i++) {da[i].x=ref[da[i].x];da[i].y=ref[da[i].y];add_edge(da[i].x,da[i].y,-(da[i].z),1);}for(int i=1;i<tot;i++) {add_edge(i,i+1,0,INF);}add_edge(0,1,0,k);add_edge(tot,tot+1,0,k);printf("%d\n",-DC.solve(0,tot+1,tot+1));return 0;
}
