rt.

复杂度 $O(kn^2)$。

#include<bits/stdc++.h>
//#define int long long
#define INF 0x3f3f3f3f
//#define INFLL 0x3f3f3f3f3f3f3f3f
#define PII pair<int,int>
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
using namespace std;
const int N=1e3+5,M=1e2+5;
int f[N][M],g[N][N],t[N],num[N][N],len;
struct node {
	int x,y;
	bool operator < (const node &tmp) const {
		return x<tmp.x||(x==tmp.x&&y<tmp.y);
	}
}; node a[N];
int get_id(int x) {
	return lower_bound(t+1,t+len+1,x)-t;
}
signed main() {
	freopen("point.in","r",stdin);
	freopen("point.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	rep(i,1,n) {
		scanf("%d%d",&a[i].x,&a[i].y);
		t[++len]=a[i].x; t[++len]=a[i].y;
	}
	sort(t+1,t+len+1);
	len=unique(t+1,t+len+1)-t-1;
	int ans=0;
	rep(i,1,n)
		f[i][0]=1,num[get_id(a[i].x)][get_id(a[i].y)]=i,g[get_id(a[i].x)][get_id(a[i].y)]=1;
	rep(i,1,len) {
		rep(j,1,len) {
			if(num[i][j]) {
				if(num[i-1][j]&&t[i]-t[i-1]==1)
					g[i][j]=max(g[i][j],g[i-1][j]+1);
				if(num[i][j-1]&&t[j]-t[j-1]==1)
					g[i][j]=max(g[i][j],g[i][j-1]+1);
				f[num[i][j]][0]=max(f[num[i][j]][0],g[i][j]);
				ans=max(ans,g[i][j]);
			}
		}
	}
	rep(j,1,m) {
//		printf("when j = %d\n",j);
		rep(i,1,n) {
			int &res=f[i][j];
			res=1;
			rep(k,1,n) {
				if(k!=i&&a[i].x>=a[k].x&&a[i].y>=a[k].y) {
					int val=a[i].x-a[k].x+a[i].y-a[k].y-1;
					if(j>=val)
						/*printf("choose %d to %d , val = %d\n",k,i,f[k][j-val]+val+1),*/res=max(res,f[k][j-val]+val+1);
				}
			}
			ans=max(ans,res+m-j);
		}
//		rep(i,1,n)
//			printf("%d ",f[i][j]);
//		puts("");
	}
	printf("%d\n",ans);
	return 0;
}