#include<bits/stdc++.h>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int d[5010];
int main(){

    int n , g , wt , val;
    in >> n >> g ;
    while(n--){
        in >> wt >> val ;
        for(int i = g ; i >= wt ; i --){
            d[i] = max(d[i] , val + d[i-wt]);
        }
    }
    out << d[g] ;
    return 0 ;
}