#include <iostream>
using namespace std;

int main(){
	int n, k; cin >> n >> k;
	int bj[n][2];
	double atl; int veg=0; int szolg[n];
	for(int i=0; i<n; i++){
		szolg[i]=0;
		cin >> bj[i][0] >> bj[i][1];
		bj[i][0]--; bj[i][1]--;
		veg=max(veg,bj[i][1]);
		atl+=(double)(bj[i][0]+bj[i][1])/2;
	}
	atl=atl/n;
	int petak=0;
	for(int i=0; i<n; i++){
		if(abs(bj[i][0]-atl)<abs(bj[i][1]-atl)){
			if(bj[i][0]<=atl) break;
			else{
				int uj=(int)(atl+0.5);
				petak+=bj[i][0]-uj;
				bj[i][0]=uj;
			}
		}
		else{
			if(bj[i][1]>=atl) break;
			else{
				int uj=(int)(atl-0.5);
				petak+=uj-bj[i][1];
				bj[i][1]=uj;
			}
		}
	}
	
	
	int jo=0;
	for(int i=0; i<n; i++){
		for(int j=bj[i][0]; j<bj[i][1]+1; j++){
			szolg[j]++;
			if(szolg[j]==n) jo++;
		}
	}
	
	
	int bal=(int)(atl-0.5);
	int jobb=(int)(atl+0.5);
	while(k!=jo){
		if(szolg[bal]<szolg[jobb]&&bal>-1){
			petak+=(veg-szolg[bal]);
			if(bal==jobb) jobb++;
			jo++; bal--;
		}
		else{
			petak+=(veg-szolg[jobb]);
			jo++; jobb++;
		}
	}
	
	cout << petak;
}