#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cctype>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <cassert>
#define _for(i,a,b) for(int i=(a);i<(b);++i)
#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
inline int read_int(){
	int t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline LL read_LL(){
	LL t=0;bool sign=false;char c=getchar();
	while(!isdigit(c)){sign|=c=='-';c=getchar();}
	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
	return sign?-t:t;
}
inline char get_char(){
	char c=getchar();
	while(c==' '||c=='\n'||c=='\r')c=getchar();
	return c;
}
inline void write(LL x){
	register char c[21],len=0;
	if(!x)return putchar('0'),void();
	if(x<0)x=-x,putchar('-');
	while(x)c[++len]=x%10,x/=10;
	while(len)putchar(c[len--]+48);
}
inline void space(LL x){write(x),putchar(' ');}
inline void enter(LL x){write(x),putchar('\n');}
const int MAXN=1005,MAXM=2005,Inf=0x7fffffff;
struct Edge{
	int to,cap,w,next;
	Edge(int to=0,int cap=0,int w=0,int next=0){
		this->to=to;
		this->cap=cap;
		this->w=w;
		this->next=next;
	}
}edge[MAXM<<1];
int head[MAXN],edge_cnt;
void Clear(){mem(head,-1);edge_cnt=0;}//边从0开始编号 
void Insert(int u,int v,int w,int c){
	edge[edge_cnt]=Edge(v,c,w,head[u]);
	head[u]=edge_cnt++;
	edge[edge_cnt]=Edge(u,0,-w,head[v]);
	head[v]=edge_cnt++;
}
struct Dinic{
	int s,t;
	int pos[MAXN],dis[MAXN];
	bool inque[MAXN];
	bool spfa(){
		mem(dis,127/3);
		queue<int>q;
		q.push(s);
		inque[s]=true,dis[s]=0,pos[s]=head[s];
		while(!q.empty()){
			int u=q.front();q.pop();
			inque[u]=false;
			for(int i=head[u];~i;i=edge[i].next){
				int v=edge[i].to;
				if(dis[u]+edge[i].w<dis[v]&&edge[i].cap){
					dis[v]=dis[u]+edge[i].w,pos[v]=head[v];
					if(!inque[v]){
						q.push(v);
						inque[v]=true;
					}
				}
			}
		}
		return dis[t]!=dis[0];
	}
	int dfs(int u,int max_flow){
		if(u==t||!max_flow)
		return max_flow;
		int flow=0,temp_flow;
		inque[u]=true;
		for(int &i=pos[u];~i;i=edge[i].next){
			int v=edge[i].to;
			if(!inque[v]&&dis[u]+edge[i].w==dis[v]&&(temp_flow=dfs(v,min(max_flow,edge[i].cap)))){
				edge[i].cap-=temp_flow;
				edge[i^1].cap+=temp_flow;
				flow+=temp_flow;
				max_flow-=temp_flow;
				if(!max_flow)
				break;
			}
		}
		inque[u]=false;
		return flow;
	}
	void MCMF(int s,int t,int &flow,LL &cost){
		this->s=s;this->t=t;
		cost=flow=0;
		int temp_flow;
		mem(inque,0);
		while(spfa()){
			temp_flow=dfs(s,Inf);
			flow+=temp_flow;
			cost+=1LL*temp_flow*dis[t];
		}
	}
}solver;
int x[MAXN],lef[MAXN],rig[MAXN],len[MAXN];
int main()
{
	Clear();
	int n=read_int(),k=read_int(),m;
	_for(i,0,n){
		lef[i]=read_int(),rig[i]=read_int(),len[i]=rig[i]-lef[i];
		x[m++]=lef[i],x[m++]=rig[i];
	}
	sort(x,x+m);
	m=unique(x,x+m)-x;
	int s=m+1,t=m+2;
	_for(i,1,m)
	Insert(i,i+1,0,k);
	Insert(s,1,0,k);Insert(m,t,0,k);
	_for(i,0,n){
		lef[i]=lower_bound(x,x+m,lef[i])-x+1;
		rig[i]=lower_bound(x,x+m,rig[i])-x+1;
		Insert(lef[i],rig[i],-len[i],1);
	}
	int flow;LL cost;
	solver.MCMF(s,t,flow,cost);
	enter(-cost);
	return 0;
}