#include <fstream>
using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

struct obiect {
    int p, w;
}v[5000];
int a[5000][10000];

void citire(int &n, int &g) {
    cin >> n >> g;

    for (int i = 1; i <= n; ++i)
        cin >> v[i].w >> v[i].p;
}

void dinamica(int n, int g) {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= g; ++j) {
            if (j - 1 + v[i].w <= g) a[i][j] = max(a[i-1][j], a[i-1][j + v[i].w] + v[i].p);
            else a[i][j] = a[i-1][j];
        }


    cout << a[n][1];
}

int main() {
    int n, g;

    citire(n, g);
    dinamica(n, g);

    return 0;
}