#include <iostream>
#include <fstream>
#define MAXW 10001
#define MAXC 10001
#define MAX 10001
#define FIN "rucsac.in"
#define FOUT "rucsac.out"

using namespace std;

int number_of_objects, W, 
    weight[MAXW], cost[MAXC],
    ProfitOptim[MAX][MAX]; 

int main() {
    ifstream fin(FIN);
    ofstream fout(FOUT);

    fin>>number_of_objects>>W;
 
    for(int i = 1; i <= number_of_objects; ++i) {

        fin>>weight[i]>>cost[i]; 
    }
 
    for(int i = 1; i <= number_of_objects; ++i) {

        for(int j = 1; j <= W; ++j) {        

                if(weight[i] <= j) ProfitOptim[i][j] = (ProfitOptim[i-1][j-weight[i]] + cost[i] > ProfitOptim[i-1][j]) ? ProfitOptim[i-1][j-weight[i]] + cost[i]: ProfitOptim[i-1][j];

                           else ProfitOptim[i][j] = ProfitOptim[i-1][j];
        }
    }

    fout<<ProfitOptim[number_of_objects][ W ];

 return(0);
}