#include <fstream>
using namespace std;

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

struct object{
    int profit,weight;
};
int dp[1001];
int main(){
    int N,G;
    in >> N >>G;
    object v[5001];
    for(int i = 0 ; i < N ;i++){
        in >> v[i].weight >> v[i].profit;
    }
    for(int i = 0 ; i < N;i++){
        for(int j = G-v[i].weight; j >=0;j--){
            if(dp[j+v[i].weight]< dp[j]+v[i].profit){
                dp[j+v[i].weight] = dp[j]+v[i].profit;
            }
        }
    }
    out << dp[G];
}