#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[5010][1010];



void knapsack(){


    for(int i=0; i<=n; i++){
        for(int w=0; w<=g; w++){
            if(i==0 || w==0){s[i][w]=0; continue;}

            if(W[i-1]<=w){
                s[i][w]=max(P[i-1]+s[i-1][w-W[i-1]], s[i-1][w] );
            }else{
            s[i][w]=s[i-1][w];
            }


        }
    }


}







//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[n][g];
fout<<s[n][g];





return 0;
}