//没发过题解，如不美观请多多谅解 //献上代码 其实这一题就是求在一个二维平面中的最长不下降子序列(LIS).

#include #include #include #include #include #include using namespace std;

int N = 510 , K = 110;

int n , k;

struct node { int x , y; bool operator< (const node &w) const { if(x == w.x) { return y < w.y; } return x < w.x; } }

node a[N];

int lon[N][K];

int main() { scanf("%d%d" , &n , &k); for(int i = 1;i <= n;i++) { scanf("%d%d" , &a[i].x , &a[i].y); } sort(a + 1 , a + 1 + n); for(int i = 1;i <= n;i++) { lon[i][k] = 1; for(int j = 0;j <= k;j++) { for(int t = 1;t < i;t++) { if(a[t].x > a[i].x || a[t].y > a[i].y) { continue; } int dx = abs(a[i].x - a[t].x); int dy = abs(a[i].y - a[t].y); int d = dx + dy - 1;

			if(j + d > k)
            {
                continue;
            }
			lon[i][j] = max(lon[i][j] , lon[t][j + d] + 1 + d);
		}
	}
}
int ans = 0;
for(int i = 1;i <= n;i++)
{
	for(int j = 1;j <= k + 1;j++)
	{
		ans = max(ans , j - 1 + lon[i][j - 1]);
	}
}
cout << ans << endl;
return 0;

}