#include <fstream>
#include <algorithm>

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

struct obiect{
    int p;
    int w;
}v[5005];

int dp[2][10005];
int main()
{
    int n, g;
    fin>>n>>g;
    for(int i=1; i<=n; i++)
        fin>>v[i].w>>v[i].p;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=g; j++){
            int lin_cur=i%2;
            int lin_ant=(i-1)%2;
            if(j-v[i].w<0)
                dp[lin_cur][j]=dp[lin_ant][j];
            else
                dp[lin_cur][j]=max(dp[lin_ant][j-v[i].w]+v[i].p, dp[lin_ant][j]);
        }

    fout<<dp[n%2][g];

    return 0;
}