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

int maxim(int a,int b){
if(a>b)return a;
return b;
}


int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");

    int nr_obiecte;
    in>>nr_obiecte;
    int greutate_maxima;
    in>>greutate_maxima;

    vector<int> greutati;
    vector<int> profituri;
greutati.push_back(0);
profituri.push_back(0);
    for(int i=0;i<nr_obiecte;i++){
        int auxgre,auxprof;
        in>>auxgre>>auxprof;
        greutati.push_back(auxgre);
        profituri.push_back(auxprof);
    }



    vector<vector<int> > dinamica(nr_obiecte+1,vector<int>(greutate_maxima+1,0) );

    for(int i=1;i<=nr_obiecte;i++){
        for(int j=0;j<=greutate_maxima;j++){
            if(j-greutati[i]>=0){
                dinamica[i][j]=maxim(dinamica[i-1][j],dinamica[i-1][j-greutati[i]]+profituri[i]);

            }
            else {
                dinamica[i][j]=dinamica[i-1][j];
            }

        }



    }


    /*for(int i=0;i<dinamica.size();i++){
        for(int j=0;j<dinamica[i].size();j++)cout<<dinamica[i][j]<<" ";
       cout<<"\n";
    }*/


    int suma_maxima=dinamica[nr_obiecte][0];

    for(int j=0;j<=greutate_maxima;j++)
    if(dinamica[nr_obiecte][j]>suma_maxima)suma_maxima=dinamica[nr_obiecte][j];

    out<<suma_maxima;
    in.close();
    out.close();
    return 0;
}