#include<bits/stdc++.h>

 using namespace std;

 const int N=,inf=1e9;

 int head[N],d[N],f[N],l[N],r[N],a[N],s=1e9,t,n,k,cnt=-,cost;

 bool v[N];

 struct node{

     int to,nex,f,w,c;

 }e[];

 void add(int x,int y,int w,int c)

 {

     e[++cnt].to=y;e[cnt].w=w;e[cnt].f=x;e[cnt].c=c;e[cnt].nex=head[x];head[x]=cnt;

     e[++cnt].to=x;e[cnt].w=;e[cnt].f=y;e[cnt].c=-c;e[cnt].nex=head[y];head[y]=cnt;

 }

 queue<int>q;

 bool spfa()

 {

     memset(f,-,sizeof(f));

     memset(d,0x3f,sizeof(d));

     memset(v,,sizeof(v));

     d[s]=;v[s]=;q.push(s);

     while(!q.empty())

     {

         int x=q.front();q.pop();v[x]=;

         for(int i=head[x];i!=-;i=e[i].nex)

         {

             int y=e[i].to;

             if(d[y]<=d[x]+e[i].c||!e[i].w)continue;

             d[y]=d[x]+e[i].c;f[y]=i;

             if(!v[y])q.push(y),v[y]=;

         }

     }

     if(d[t]>1e9)return ;

     int flow=inf;

     for(int i=f[t];i!=-;i=f[e[i].f])

     flow=min(flow,e[i].w);

     for(int i=f[t];i!=-;i=f[e[i].f])

     e[i].w-=flow,e[i^].w+=flow,cost+=e[i].c*flow;

     return ;

 }

 int main()

 {

     scanf("%d%d",&n,&k);int num=;

     memset(head,-,sizeof(head));

     for(int i=;i<=n;++i)

     {

         scanf("%d%d",&l[i],&r[i]);

         a[++num]=l[i];a[++num]=r[i];

     }

     sort(a+,a++num);

     num=unique(a+,a++num)-a-;

     for(int i=;i<=n;++i)

     {

         int x=r[i]-l[i];

         l[i]=lower_bound(a+,a++num,l[i])-a;

         r[i]=lower_bound(a+,a++num,r[i])-a;

         add(l[i],r[i],,-x);

     }

     for(int i=;i<num;++i)

     add(i,i+,k,);t=num+;

     add(num,t,k,);

     add(,,k,);s=;

     while(spfa());

     printf("%d\n",-cost);

     return ;

 }