#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

#define VI vector<int>
#define VP vector<pair<int,int>>
#define VVI vector<VI>

int N, G;
VP obiect;
VVI dp;

int main() {
    fin >> N >> G;
    obiect = VP(N+2);
    for (int i = 1; i <= N; ++i) {
        fin >> obiect[i].first >> obiect[i].second;
    }
    dp = VVI (2, VI(G + 3));
    for (int i = 1; i <= N; ++i)  {
        swap(dp[0], dp[1]);
        for (int cw = 0; cw <= G; ++cw) {
            if (cw - obiect[i].first >= 0) 
                dp[1][cw] = max(dp[0][cw], dp[0][cw - obiect[i].first] + obiect[i].second);
            else 
                dp[1][cw] = dp[0][cw];
        }
    }   
    fout << dp[1][G];
}