#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define eb emplace_back
using ii = pair<int, int>;
int N, M, to_remove, W[1000005], E[1000005], to[2000005];
ii frnt[1000005], back[1000005];
vector<int> vec;
namespace ufds {
int lnk[2000005], sz[2000005];
void init(int n) {
iota(lnk + 1, lnk + 1 + n, 1);
fill(sz + 1, sz + 1 + n, 1);
}
int find(int x) {
if (x == lnk[x]) return x;
return lnk[x] = find(lnk[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
lnk[b] = a;
}
};
void counting_sort(vector<int> vec) {
vector<int> freq(N + 1, 0);
int idx = 0;
for (int i : vec) freq[i]++;
for (int i = 0; i <= N; i++) {
for (int j = 0; j < freq[i]; j++) vec[idx++] = i;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++) {
cin >> W[i] >> E[i];
frnt[i - 1] = mp(W[i], i);
back[i - 1] = mp(E[i], N + i);
}
sort(frnt, frnt + N);
sort(back, back + N);
for (int i = 1; i <= N; i++) {
// i_f
auto it = upper_bound(frnt, frnt + N, mp(E[i], (int)1e9));
auto it2 = upper_bound(back, back + N, mp(E[i], (int)1e9));
if (it != frnt + N && it2 != back + N) {
to[i] = (it->first < it2->first ? it->second : it2->second);
} else if (it == frnt + N && it2 == back + N) {
} else {
to[i] = it == frnt + N ? it2->second : it->second;
}
// i_b
it = upper_bound(frnt, frnt + N, mp(W[i], (int)1e9));
it2 = upper_bound(back, back + N, mp(W[i], (int)1e9));
if (it != frnt + N && it2 != back + N) {
to[i + N] = (it->first < it2->first ? it->second : it2->second);
} else if (it == frnt + N && it2 == back + N) {
} else {
to[i + N] = it == frnt + N ? it2->second : it->second;
}
}
ufds::init(2 * N);
for (int i = 1; i <= 2 * N; i++) {
if (to[i]) ufds::unite(i, to[i]);
}
for (int i = 1; i <= 2 * N; i++) {
if (i == ufds::find(i)) vec.pb(ufds::sz[i]);
if (!to[i]) to_remove = ufds::sz[ufds::find(i)];
}
counting_sort(vec);
vec.erase(find(vec.begin(), vec.end(), to_remove));
int ans = 2 * M + to_remove;
for (int i = 0; i < min((int)vec.size(), M); i++) {
ans += vec[i];
}
if (M > (int)vec.size() && (M - (int)vec.size()) % 2 == 1) ans--;
cout << ans << '\n';
}
