#include <bits/stdc++.h>



using namespace std;

ifstream fin("rucsac.in");

ofstream fout("rucsac.out");



struct object

{
    short weight, value;
};

int n,g;

object lst[5003];

int dp[2][10003];

void citire()
{
    fin>>n>>g;
    for(int i=1; i<=n; ++i)
    {
        fin>>lst[i].weight;
        fin>>lst[i].value;
    }
}

int main()
{
    citire();
    for(int i=1; i<=n; ++i)
    {
        for(int j=0; j<=g; ++j)
        {
            if(j-lst[i].weight<0)
                dp[i%2][j] = dp[!(i%2)][j];
            else
            {
                int bef = j-lst[i].weight;
                dp[i%2][j] = max(dp[!(i%2)][bef] + lst[i].value, dp[!(i%2)][j]);
            }
        }


    }
        fout<<dp[10%2][g];
    return 0;

}