dp:完全背包：三维，二维，一维

//完全背包
#include<iostream>
using namespace std;

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

int main(void) {
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];
    //朴素版：时间复杂度较高
                // for(int i=1;i<=n;i++)
                //     for(int j=1;j<=m;j++)
                //         for(int k=0;k*v[i]<=j;k++)
                //             f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);   //i只表示前i个物品选 不代表个数 所以是f[i-1] 不是f[i-k]
    //优化成二维 后边的j-k*v[i]项可等价替换 具体见ipad笔记   f(i,j)=max(f(i-1,j)+0w,f(i-1,j-v)+w,  f(i-1,j-2v)+2w,.....) 前边一项始终是i-1
    //                                               f(i,j-v)=max(          f(i-1,j-v)+0w ,f(i-1,j-2v)+1w
                // for(int i=1;i<=n;i++)
                //     for(int j=1;j<=m;j++) {
                //         f[i][j]=f[i-1][j];
                //         if(j>=v[i])
                //             f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);  //神似01背包
                //     }
                // cout<<f[n][m]<<endl;
    //优化成一维,优化方法与01背包一致
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)   //因此时需要第i层的j-v[i]，因此从小到大枚举即可
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m];
    return 0;
}