//
//  main.cpp
//  C++ - teste
//
//  Created by Filip Cuciuc on 03/02/2020.
//  Copyright © 2020 Filip Cuciuc. All rights reserved.
//

//#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <map>
//#include "MED.h"
using namespace std;

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

int n, G, rez, Pmax = 0;
int g[5005], p[5005], dp[10005];

int main() {
    cin >> n >> G;
    for (int i = 1; i <= n; i++) {
        cin >> g[i] >> p[i];
        for (int j = G -g[i]; j >= 0; j--) {
            dp[j + g[i]] = max(dp[j + g[i]], dp[j] + p[i]);
            if (dp[j + g[i]] >= Pmax) {
                Pmax = dp[j + g[i]];
            }
        }
    }
    
    cout << Pmax;
    
    return 0;
}