#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <algorithm>
#include <limits.h>
using namespace std;
#define NMAX 5000
#define GMAX 10000

void print_matrix(char **matrix, int n, int m, std::ostream &out) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            out << matrix[i][j] << ' ';
        }
        out << '\n';
    }
}

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

int n, g;
int w[NMAX], p[GMAX];
int dp[GMAX+1];

int main(){
    fin>>n>>g;
    for(int i = 0; i<n; i++)
        fin>>w[i]>>p[i];
    for(int num = 1; num<=n; num++){
        for(int weight = g; weight>=1; weight--){
            dp[weight] = max(weight-w[num-1] < 0 ? 0 : dp[weight-w[num-1]] + p[num-1], dp[weight]);
        }
    }
    fout << dp[g];
    return 0;
}