dp：01背包 二维加一维

//01背包：按照y总分析所写 用于学习记录
#include<iostream>
using namespace std;

const int N=1010;
int v[N],w[N];
int f[N];
int n,m;

int main(void) {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    //二维写法：
    /*        // f[0][1-m]  前0个物品选 总体积不超过1-m 的最大价值为0
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++) {
                    f[i][j]=f[i-1][j]; //左边的情况一定存在
                    if(v[i]<=j)    //右边情况只有当j大于v[i]时 才可取
                        f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
                }
            cout<<f[n][m]<<endl;*/
    //一维写法：   所有更新只涉及i-1层，因此可用滑动数组变为一维
    //           f[j]直接取i-1层的f[j] 直接删除即可
    //           因j大于v[i]时才可更新 因此改变循环 撤掉if  :for(int j=v[i];j<=m;j++);
    //           因此时更新时f[j-v[i]] j是从小更新到大的 因此j-v[i]可能在第i层更新了 但我们需要i-1层的j-v[i] 因此从大到小更新 可解决这一问题
                for(int i=1;i<=n;i++)
                    for(int j=m;j>=v[i];j--)
                        f[j]=max(f[j],f[j-v[i]]+w[i]);
                cout<<f[m]<<endl;
    return 0;
}