#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int dp[10001][2],stare = 0;

int main()
{

    int n,g;
    fin>>n>>g;

    int w[5001],p[5001];

    for(int i=1;i<=n;i++)
        fin>>w[i]>>p[i];


    for(int i=1;i<=n;i++){

        for(int j=1;j<=g;j++)
            if(j-w[i] >=0)
                dp[j][stare] = (dp[j][1-stare]) > (dp[j-w[i]][1-stare] + p[i]) ? dp[j][1-stare] : (dp[j-w[i]][1-stare] + p[i]);
            else dp[j][stare] = dp[j][1-stare];
        stare = 1-stare;

    }

    fout<<dp[g][1-stare];

    return 0;
}