#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], sol=0;



void knapsack(){


    for(int i=n-1; i>=0; 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];
            }

            sol=max(sol, s[w+W[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];
}
s[g]=0;
knapsack();

cout<<sol;
fout<<sol;





return 0;
}