#include <bits/stdc++.h>

using namespace std;

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

int w[5005], p[5005];

int n, gr;
int d[2][10005];

int main()
{
    int i, j, now = 0;

    f >> n >> gr;

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

    for(i = 1; i <= n; i ++) {
        for(j = 1; j <= gr; j ++) {
            if(w[i] <= j)
                d[now][j] = max(d[1 - now][j], d[1 - now][j - w[i]] + p[i]);
        }
        now = 1 - now;
    }

    g << d[1 - now][gr] << '\n';

    f.close();
    g.close();

    return 0;
}