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

ifstream f("rucsac.in"); ofstream g("rucsac.out");
int n,k,a[3][10005],w[5005],p[5005];

int main() {
    int i;
    f>>n>>k;
    for(i = 1; i <=n; ++i) {
        f>>w[i]>>p[i];
    }
    a[1][0] = 0;
    for(i = 1; i <= k; ++i) {
        if (i >= w[1]) {
            a[1][i] = p[1];
        }
        else {
            a[1][i] = 0;
        }
    }
    for(i = 2; i <= n; ++i) {
        for(int j = k; j > 0; --j) {
            if (j >= w[i]) {
                a[2][j] = max(a[1][j],a[1][j-w[i]] + p[i]);
                a[1][j] = a[2][j];
            }
            else {
                a[2][j] = a[1][j];
            }
        }
    }
    g<<a[2][k];
    return 0;
}