#include<iostream>
#include<fstream>
#define maxr 10002
#define maxn 5002
using namespace std;

int n, r, w[maxn], v[maxn], sol[maxr], sumx;

int main (){
    
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    
    f>>n>>r;
    for(int i = 1; i<=n; i++){
        f>>w[i]>>v[i];
    }
    f.close();
    
    for(int i = 1; i<=n; i++){
        for(int j = r - w[i]; j>=0; j--){
            if(sol[j+w[i]] < sol[j] + v[i]){ 
                sol[j+w[i]] = sol[j] + v[i];
                if(sol[j+w[i]] > sumx) sumx = sol[j+w[i]];
            }
        }
    }
    
    g<<sumx;
    g.close();
    
    return 0;
}