#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
//#define int long long
using namespace std;
const int mod=998244353,mxn=2e6+5,inf=1e9,minf=-1e9,lg=25;
int n,m,k,x,y;
int dp[mxn+10],vis[mxn+10];
pii nxt[mxn+10];
int cnt=0;
void dfs(int cur){
//memory?
while(!vis[cur]){
vis[cur]=1;
if(vis[nxt[cur].f])return;
cnt+=nxt[cur].s;
cur=nxt[cur].f;
}
/*
if(vis[cur])return;
vis[cur]=1;
if(!vis[nxt[cur].f])dfs(nxt[cur].f),dp[cur]=dp[nxt[cur].f]+nxt[cur].s;*/
}
int32_t main(){
fastio
cin>>n>>m;
for(int i=0;i<=mxn;i++)dp[i]=0,nxt[i]={i+1,0};
for(int i=0;i<n;i++){
int a,b;cin>>a>>b;
nxt[a]={b+1,1},nxt[b]={a+1,1};
}
vis[mxn+1]=1;
cnt=0;
dfs(1);
int ans=cnt;
vector<int>have;
for(int i=1;i<=mxn;i++)if(!vis[i]){//comp
cnt=0;
dfs(i),have.pb(cnt);
}
sort(rall(have));
for(int i=0;i<have.size()&&m>0;i++)m--,ans+=(3+have[i]);
//other
if(m%2)ans++,m--;
ans+=(m*2);
cout<<ans<<'\n';
}
/*
putting a new teleporter down allow us to repeat any part of the sequence even if its not on the orignial path
a1 b1 X a2 b2 (order of teleportation a1->a2->b2->b1->X->a2->a1->b1->b2)
a1 b1 c1 X a2 b2 c2 (a1,a2,b2,b1,c1,c2....) odd number teleporter wont do anything
a1 b1 c1 d1 X a2 b2 c2 d2
a1,a2,b2,b1,c1,c2,d2,d1,X,a2,a1,b1,b2,c2,c1,d1,d2
with 4 or 2 it will execute X 1 times
put m tp(m is even)
cost+=(X+(2*m))
not original path{
can split in comp?
if its not used in orginal path then it has to be covered by some range l(X)r where no range is sticking out of it
if we put teleporter after l (x,r,l,tpback)
we can only put 1 tp for each comp
cost+=3+length
}
sort all comp
*/
