#include<iostream>//01背包问题
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010;
int w[N],v[N];
int n,m;
int f[N][N];//f[i][j]存储只考虑第1到i个物品且总体积不超过j的选项的集合的最大价值
int main()
{
    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=0;j<=m;j++)
        {
            f[i][j]=f[i-1][j];//f[i-1][j]存储不选择i的选项
            if(j>=v[i])f[i][j]=max(f[i-1][j],(f[i-1][j-v[i]]+w[i]));//选择i的选项
        }//当j比Vi小时第i个物品一定不能选
    cout<<f[n][m]<<endl;
    return 0;
}
//对代码进行优化 f[N]即总体积不超过j的选项的集合的最大价值
//for(int i=1;i<=n;i++)进行n层计算且每一层考虑1到i个物品
//for(int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+w[i]);
//为了保证此时的 f[j-v[i]]是第i-1层计算出的，所以需要j--倒叙计算
//如果j++顺序计算，则f[j-v[i]]会比f[j]先计算出，则此时的f[j-v[i]]是第i层的，与原式不等价