#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int p[10001],w[10001],dp[10001][10001],n,m,x;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        fin>>p[i]>>w[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int cw=0;cw<=m;cw++)
        {
            dp[i][cw]=max(p[i]+dp[i-1][cw-w[i]],0+dp[i-1][cw]);
        }
    }
    fout<<dp[n][m];
}