#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1100000;
int n, r, s[N], a[N][2];
int sim() {
int cnt = 0;
for (int i = 1; i <= r; i++) {
for (int j = 2; j <= n; j++)
if (a[j][0] > a[j][1])
swap(a[j][0], a[j][1]);
if (a[1][0] < a[1][1])
swap(a[1][0], a[1][1]);
if (a[1][0] == s[1])
cnt++;
for (int j = 2; j <= n; j++)
if (a[j][0] == s[1])
cnt++;
int t = a[1][0];
for (int j = 1; j < n; j++)
a[j][0] = a[j + 1][0];
a[n][0] = t;
}
return cnt;
}
int c[N][3];
int gt(int x) {
if (x < s[1]) return 0;
if (x > s[1]) return 2;
if (x == s[1]) return 1;
// wtf is this shit?
return -1;
}
int sim2() {
for (int i = 0; i <= 4 * n; i++)
for (int j = 0; j < 3; j++)
c[i][j] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < 2; j++)
a[i][j] = gt(a[i][j]);
int c0 = 0, c1 = 0, c2 = 0, x = a[1][0], y = a[1][1], t = 0;
for (int i = 2; i <= n; i++)
for (int j = 0; j < 2; j++)
c[i - 1][a[i][j]]++;
auto step = [&]() {
if (x > y) swap(x, y);
c[t + n][y]++;
t++;
c0 += c[t][0];
c1 += c[t][1];
c2 += c[t][2];
if (c0 > 0) {c0--; y = 0;}
else if (c1 > 0) {c1--; y = 1;}
else if (c2 > 0) {c2--; y = 2;}
};
int ans = 3 * n + 1;
for (int i = 1; i <= 2 * n; i++) {
bool here = (x == 1 || y == 1);
step();
bool there = (x == 1 || y == 1);
if (here && !there) ans -= n;
}
for (int i = 2 * n + 1; i <= 3 * n; i++) {
bool here = (x == 1 || y == 1);
step();
bool there = (x == 1 || y == 1);
if (here && !there) ans -= n;
if (there) {
ans -= r - i;
break;
}
}
return ans;
}
int sim3(int x) {
for (int i = 1; i <= n; i++)
for (int j = 0; j < 2; j++)
a[i][j] = gt(a[i][j]);
int c1 = 0, c2 = 0, ptr = n, base = x + 3 * n;
for (int i = 1; i <= 2 * n; i++) {
ptr = (ptr + n - 2) % n + 1;
if (a[ptr][0] == 1) c1++;
if (a[ptr][1] == 1) c1++;
if (a[ptr][0] == 2) c2++;
if (a[ptr][1] == 2) c2++;
a[ptr][0] = a[ptr][1] = 0;
if (c1 + c2 != 0 && ptr != 1) {
if (c2 > 0) {
c2--;
a[ptr][0] = 2;
} else {
c1--;
a[ptr][0] = 1;
}
}
if (c1 > 0) base--;
}
return base;
}
int get(int i) {
a[i][0] = s[1];
for (int j = 1; j < i; j++) {
a[j][0] = s[2 * j];
a[j][1] = s[2 * j + 1];
}
a[i][1] = s[2 * i];
for (int j = i + 1; j <= n; j++) {
a[j][0] = s[2 * j - 1];
a[j][1] = s[2 * j];
}
if (s[1] <= n + 1)
return sim2();
return sim3(i);
//return i - sim() + 3 * n;
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> r;
r = (r - 2 * n) % n + 2 * n;
for (int i = 1; i <= 2 * n; i++)
cin >> s[i];
if (s[1] == 1) {
cout << n;
return 0;
}
array<int, 2> ans = {n, -n};
int L = get(1);
int R = get(n);
for (int k = 1; k <= 4; k++) {
int kl = (k - 1) * n + 1;
int kr = kl + n - 1;
if (kr < L || kl > R) continue;
int tl = 0, tr = n + 1;
while (tr - tl > 1) {
int tk = (tl + tr) / 2;
if (get(tk) < kl) tl = tk;
else tr = tk;
}
if (tr == n + 1) continue;
int val = get(tr);
if (val > kr) continue;
tl = tr;
tr = n + 1;
while (tr - tl > 1) {
int tk = (tl + tr) / 2;
if (get(tk) == val) tl = tk;
else tr = tk;
}
ans = min(ans, {val - kl + 1, -tl});
}
cout << -ans[1];
}
