在一个二维平面内，给定 n 个整数点 (xᵢ,yᵢ)，此外你还可以自由添加 k 个整数点。

你在自由添加 k 个点后，还需要从 n+k 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且横坐标、纵坐标值均单调不减，即： xᵢ₊₁−xᵢ = 1, yᵢ₊₁ = yᵢ 或 yᵢ₊₁−yᵢ = 1, xᵢ₊₁ = xᵢ ，请给出满足条件的序列的最大长度。

【输入格式】

第一行两个正整数 n, k 分别表示给定的整点个数、可自由添加的整点个数。

接下来 n 行，第 i 行两个正整数 xᵢ , yᵢ 表示给定的第 i 个点的横纵坐标。

【输出格式】

输出一个整数表示满足要求的序列的最大长度。

【数据范围】

保证对于所有数据满足：1≤n≤500，0≤k≤100。对于所有给定的整点，其横纵坐标 1≤xᵢ, yᵢ≤10⁹，且保证所有给定的点互不重合。对于自由添加的整点，其横纵坐标不受限制。

【输入样例】

8 2
3 1
3 2
3 3
3 6
1 2
2 2
5 5
5 3

【输出样例】

8

// 爱码岛编程（P8816）
#include <bits/stdc++.h>
using namespace std;

const int MANX = 510;
//点
struct Point {
    int x;
    int y;
} a[MANX];

bool cmp(Point p1, Point p2) {
    if (p1.x != p2.x) {
        return p1.x < p2.x;
    } else {
        return p1.y < p2.y;
    }
}

int dis[MANX][MANX];
int dp[MANX][110];
int n, m; // m表示自由点的总数

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    //先排序
    sort(a + 1, a + n + 1, cmp);
    // 计算距离（可以放自由点的数量）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            dis[i][j] = a[i].x - a[j].x + a[i].y - a[j].y - 1;
        }
    }
    // 动态转移
    for (int i = 1; i <= n; i++) {
        for (int k = 0; k <= m; k++) {
            dp[i][k] = k + 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[i].x >= a[j].x && a[i].y >= a[j].y) {
                for (int k = 0; k <= m; k++) {
                    if (k - dis[i][j] >= 0 && dis[i][j] >= 0)
                        dp[i][k] =
                            max(dp[i][k], dp[j][k - dis[i][j]] + dis[i][j] + 1);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, dp[i][m]);
    }
    cout << ans << endl;
    return 0;
}