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

#define MAXN 5010

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int n, G;
int w[MAXN], p[MAXN];
int pmax[10010];

int main() {
    f >> n >> G;
    for (int i = 1; i <= n; i++) {
        f >> w[i] >> p[i];
    }

    pmax[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = G; j >= w[i]; j--) {
            if (pmax[j - w[i]] != 0) {
                pmax[j] = max(pmax[j - w[i]] + p[i], pmax[j]);
            }
        }
    }

    int mx = 0;
    for (int i = 1; i <= G; i++) {
        if (mx < pmax[i]) {
            mx = pmax[i];
        }
    }
    g << mx - 1;

    return 0;
}