#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 (N + 3, VI(G + 3));
    for (int i = 1; i <= N; ++i)  {
        for (int cw = 0; cw <= G; ++cw) {
            if (cw - obiect[i].first >= 0) 
                dp[i][cw] = max(dp[i - 1][cw], dp[i - 1][cw - obiect[i].first] + obiect[i].second);
            else 
                dp[i][cw] = dp[i - 1][cw];
        }
    }   
    fout << dp[N][G];
}