#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
struct edge
{
	LL x,cap,cost,rev;
};
vector<edge> e[N];
int n,m,s,t;
bool st[N];
LL d[N];
int it[N];
void add(int a,int b,LL c,LL d)
{
	e[a].push_back({b,c,d,(LL)e[b].size()});
	e[b].push_back({a,0,-d,(LL)e[a].size() - 1});
}
void spfa()
{
	memset(d,0x3f,sizeof d);
	queue<int> q;
	d[s] = 0;
	q.push(s);
	st[s] = 1;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		st[u] = 0;
		for(auto t : e[u])
			if(t.cap > 0 && d[t.x] > d[u] + t.cost)
			{
				d[t.x] = d[u] + t.cost;
				if(!st[t.x]) q.push(t.x),st[t.x] = 1;
			}
	}
}
LL res;
LL dfs(int u,LL f)
{
	if(u == t) return f;
	st[u] = 1;
	for(int &i = it[u]; i < e[u].size(); i ++)
	{
		edge &t = e[u][i]; 
		if(!st[t.x] && d[u] + t.cost == d[t.x] && t.cap > 0)
		{
			LL d = dfs(t.x,min(f,t.cap));
			if(d > 0)
			{
				t.cap -= d;
				e[t.x][t.rev].cap += d;
				res += d * t.cost;
				st[u] = 0; 
				return d;
			}
		}
	}
	st[u] = 0; 
	return 0;
}
LL dinic() 
{
	LL flow = 0;
	while(1)
	{
		spfa();
		if(d[t] == INF) break;
		memset(it,0,sizeof it);
		LL d = dfs(s,1e18);
		while(d > 0)
		{
			flow += d;
			d = dfs(s,1e18);
		}
	}
	return flow;
}
int a[N],b[N],c[N],l[N];
int main()
{
	cin>>n>>m;
	for(int i = 1; i <= n; i ++) cin>>a[i]>>b[i],c[2 * i - 1] = a[i],c[2 * i] = b[i],l[i] = abs(b[i] - a[i]);
	sort(c + 1,c + 2 * n + 1);
	int cnt = unique(c + 1,c + 2 * n + 1) - c - 1;
	s = 0,t = cnt + 1;
	for(int i = 0; i <= cnt; i ++) add(i,i + 1,m,0);
	for(int i = 1; i <= n; i ++) a[i] = lower_bound(c + 1,c + cnt + 1,a[i]) - c,b[i] = lower_bound(c + 1,c + cnt + 1,b[i]) - c;
	for(int i = 1; i <= n; i ++) if(a[i]>b[i]) swap(a[i],b[i]);
	for(int i = 1; i <= n; i ++) add(a[i],b[i],1,-l[i]);
	dinic();
	cout<<-res<<endl;
	return 0;
}