#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];
vector<int> vec;
vector<ii> frnt, back;
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;
}
};
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.eb(W[i], i);
back.eb(E[i], N + i);
}
sort(frnt.begin(), frnt.end());
sort(back.begin(), back.end());
for (int i = 1; i <= N; i++) {
// i_f
auto it = upper_bound(frnt.begin(), frnt.end(), mp(E[i], (int)1e9));
auto it2 = upper_bound(back.begin(), back.end(), mp(E[i], (int)1e9));
if (it != frnt.end() && it2 != back.end()) {
to[i] = (it->first < it2->first ? it->second : it2->second);
} else if (it == frnt.end() && it2 == back.end()) {
} else {
to[i] = it == frnt.end() ? it2->second : it->second;
}
// i_b
it = upper_bound(frnt.begin(), frnt.end(), mp(W[i], (int)1e9));
it2 = upper_bound(back.begin(), back.end(), mp(W[i], (int)1e9));
if (it != frnt.end() && it2 != back.end()) {
to[i + N] = (it->first < it2->first ? it->second : it2->second);
} else if (it == frnt.end() && it2 == back.end()) {
} else {
to[i + N] = it == frnt.end() ? it2->second : it->second;
}
}
ufds::init(2 * N);
for (int i = 1; i <= 2 * N; i++) {
if (to[i]) ufds::unite(i, to[i]);
}
assert(count(to + 1, to + 1 + 2 * N, 0) == 1);
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)];
}
sort(vec.begin(), vec.end(), greater<int>());
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';
}
