01背包的变种，只是加入了抢劫和不抢的区别。

需要注意的是，如果抢劫的话，那抢劫一定会在购买之前。

我们用f[i]记录消费为i时的最优解，f2[i]储存到第i个物品时的最优解，则答案即为f[m]与f2[n]中的最大值。

（其实是f2[n]，能白嫖为什么要买呢？但数组还是要开的...）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define str string
#define db double
#define F(n) for(int i=1;i<=n;i++)

const int dx[5]={0,1,-1,0,0};
const int dy[5]={0,0,0,1,-1};

const int LXB=2e5+10;


int n,m,k,l,t;
int a[LXB],w[LXB],f[LXB],f2[LXB];
string ss;
char p;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int T=1;
    while(T--){
        cin>>n>>m;
        F(n){
            cin>>w[i]>>a[i];
        }
        F(n){
            t++;
            f2[t]=max(f2[t-1],f[m]+a[i]);//在花钱之前抢劫
            for(int j=m;j>=w[i];j--){
                f[j]=max(f[j],f[j-w[i]]+a[i]);
            }
        }
    }
    cout<<max(f[m],f2[n]);
    return 0;
}