#include <iostream>
#include <fstream>

using namespace std;


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

const int MAX_N=5001;
const int MAX_G=10000;

struct t_object{
    int greutate;
    int profit;
};

int memo[MAX_N][MAX_G];

int dp_profit(int idx ,int capacitate, t_object objs[]){
    if(idx==0)
        return 0;
    if(capacitate==0)
        return 0;
    if(memo[idx][capacitate]!=0)
        return memo[idx][capacitate];
    if(objs[idx].greutate>capacitate){
        memo[idx][capacitate]=dp_profit(idx-1,capacitate,objs);
        return memo[idx][capacitate];
    }
    // cazul 1 - nu luam obiectul

    int profit=dp_profit(idx-1,capacitate,objs);

    // cazul 2 - lauma obiectul

    int new_capacitate=capacitate-objs[idx].greutate;
    int profit2=objs[idx].profit+dp_profit(idx-1,new_capacitate,objs);
    memo[idx][capacitate]=max(profit, profit2);
    return memo[idx][capacitate];
}

int main()
{
    int nr_elem;
    int max_gr;
    t_object objs[MAX_N];

    fin>>nr_elem;
    fin>>max_gr;

    for(int i=1;i<=nr_elem;i++){
        int profit;
        int greutate;

        fin>>greutate;
        fin>>profit;
        t_object obj={greutate,profit};
        objs[i]=obj;
    }
    fout<<dp_profit(nr_elem,max_gr,objs);
    return 0;
}