#include <fstream>

using namespace std;

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

const int max_n=5001;
const int max_g=10001;

struct obj{
    int weight;
    int profit;
}v[101];

int memo[max_n][max_g];

int dp_profit(int idx, int capacitate, obj v[], int memo[][max_g])
{
    if(idx==0)
        return 0;
    if(capacitate==0)
        return 0;
    if(memo[idx][capacitate]!=0)
        return memo[idx][capacitate];
    obj curr_obj=v[idx];
    if(curr_obj.weight>capacitate)
        return dp_profit(idx-1,capacitate,v,memo);
    int profit1=dp_profit(idx-1,capacitate,v,memo);
    int profit2=curr_obj.profit+dp_profit(idx-1,capacitate-curr_obj.weight,v,memo);
    memo[idx][capacitate]=max(profit1,profit2);
    return max(profit1,profit2);
}

int main()
{
    int n,g;
    fin>>n>>g;
    for(int i=1;i<=n;i++)
    {
        int curr_g, curr_p;
        fin>>curr_g>>curr_p;
        obj obiect={curr_g,curr_p};
        v[i]=obiect;
    }
     fout<<dp_profit(n,g,v,memo);
    return 0;
}