题解 100% AC

#include <bits/stdc++.h>
using namespace std;
int n,k,ans;
pair<int,int>p[505];
int dp[505][505];
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>p[i].first>>p[i].second;
    sort(p+1,p+n+1,[](pair<int,int>a,pair<int,int>b){if(a.first==b.first)return a.second<b.second;return a.first<b.first;});
    for(int i=1;i<=n;i++)for(int j=0;j<=k;j++)dp[i][j]=j+1;
    for(int i=2;i<=n;i++){
    	for(int j=1;j<i;j++){
    		if(p[j].second>p[i].second)continue;
    		int d=p[i].first-p[j].first+p[i].second-p[j].second-1;
    		for(int l=d;l<=k;l++)dp[i][l]=max(dp[i][l],dp[j][l-d]+d+1);
		}
		ans=max(ans,dp[i][k]);
	}
	cout<<ans;
	return 0;
}