#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ft first
#define sc second

ifstream fin("rucsac.in"); ofstream fout("rucsac.out");
int n, g, W[5010], P[5010];

int s[1010];



void knapsack(){


    for(int i=0; i<n; i++){
        for(int w=g-W[i]; w>=0; w--){

            if( s[w+W[i]]< s[w]+P[i] ){
                s[w+W[i] ]=s[w]+P[i];
            }


        }
    }


}







//X-first, Y-second6 7 1 4
int main(){
fin>>n>>g;


for(int i=0; i<n; i++){
    fin>>W[i]>>P[i];
}

knapsack();

cout<<s[g];
fout<<s[g];





return 0;
}