#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <fstream>
#include <chrono>
using namespace std;
using namespace std::chrono;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<ull> vull;
typedef vector<vull> vvull;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vstring;
typedef vector<double> vdouble;

#define fs first
#define sc second
#define pb push_back
// forward strict for, most common
#define fors(i, a, n) for (int i = (int) (a); i < (int) (n); ++i)
// forward inclusive for
#define fori(i, a, n) for (int i = (int) (a); i <= (int) (n); ++i)
// backward for, inclusive
#define forb(i, n, a) for (int i = (int) (n); i >= (a); --i)

class Problem {
public:
    int n, g;
    vint dp, dp1;
    void solve() {
        ifstream in("rucsac.in");
        ofstream out("rucsac.out");

        in >> n >> g;
        vint w(n), p(n);        
        fors(i, 0, n)
            in >> w[i] >> p[i];

        dp.resize(g+1);
        
        dp[w[0]] = p[0];
//        print_dp();
        fors(i, 1, n)
        {
            dp1 = dp;
            dp = vint(g + 1);
            fori(g_, 0, g)
            {
                dp[g_] = dp1[g_];
                if (g_ - w[i] >= 0) dp[g_] = max(dp1[g_], dp1[g_ - w[i]] + p[i]);
            }
//            cout << "index " << i << endl;
//            print_dp();
        }

        int res = 0;
        fori(g_, 0, g)
            res = max(res, dp[g_]);

        out << res << endl;
    }
    
    void print_dp() {
        cout << "dp: " << endl;
        for(int u : dp) cout << u << " ";
        cout << endl;
    }
};

int main() {
    Problem p;
    p.solve();
    return 0;
}