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

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

typedef long long ll;
int N, G;
int g[10001];
int p[10001];
int main() 
{
    fin >> N >> G;
    for (int i = 0; i < N; i++) {
        int x, y;
        fin >> x >> y;
        g[i] = x;
        p[i] = y;
    }

    int l = 0;
    vector<vector<int>> d(2, vector<int>(G + 1, 0));
    for (int i = 0; i < N; i++) {
        l = 1 - l;
        for (int j = 0; j <= G; j++) {
            if (j - g[i] < 0) {
                d[l][j] = d[1 - l][j];
            }
            else {
                d[l][j] = max(d[1 - l][j], d[1 - l][j - g[i]] + p[i]); 
            }
        }
    }
    fout << d[l][G];
}