//一道比较模板的dp；
//40分做法，人人都会，即只打k=0的情况；
#include<bits/stdc++.h>
using namespace std;


struct node
{
    int x, y;
}pos[510];
int n, k;
int f[510];
int dp[510][110];

bool cdist(int x1, int y1, int x2, int y2)
{
    if(x1 == x2 && y2 - y1 == 1)
    return true;
    if(y1 == y2 && x2 - x1 == 1)
    return true;

    return false;
}

bool cmp(node a, node b)
{
    if(a.x == b.x)
    return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
    cin >> pos[i].x >> pos[i].y;

    sort(pos + 1, pos + 1 + n, cmp);//先把坐标排序；

    for(int i = 1;i <= n;i++)
    {
        f[i] = 1;
        for(int j = 0;j < i;j++)
        {
            if(cdist(pos[j].x,pos[j].y,pos[i].x, pos[i].y))
            f[i] = max(f[i], f[j] + 1);
        }
    }//类似于最长上升子序列；

    int ans = 0;
    for(int i = 1;i <= n;i++)
    ans = max(ans, f[i]);

    if(k == 0)
    {
        cout << ans << endl;
        return 0;
    }

}

//100分做法#include<bits/stdc++.h>
using namespace std;

int n, k;
struct node
{
    int x, y;
}a[510];
int f[510][110], ans = 0;//设f[i][j]表示选前i个点为末尾，加了j个点时的最大值；

bool cmp(node a, node b)
{
    if(a.x == b.x)
    return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i++)
    cin >> a[i].x >> a[i].y;

    sort(a + 1, a + 1 + n, cmp);


    for(int i = 1;i <= n;i++)
    {
        for(int j = 0;j <= k;j++)
        {
            f[i][j] = j + 1;//初始化
            for(int p = 1;p < i;p++)
            {
                if(a[i].y < a[p].y)
                continue;//不符合题目要求，直接退出；
                int cnt = a[i].x - a[p].x + a[i].y - a[p].y - 1;//计算要加多少个点；
                if(cnt > j)
                continue;//特殊情况判掉
                f[i][j] = max(f[i][j], f[p][j - cnt] + cnt + 1);
                //转移
            }
        }
    }


    for(int i = 1;i <= n;i++)
        for(int j = 0;j <= k;j++)
            ans = max(ans, f[i][j] + k - j);
    //打擂台更新答案，注意有k-j个点还没有加，需要加上；

    cout << ans << endl;


    return 0;
}