#include <fstream>

using namespace std;

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

struct pepene{
    int w, p;
}a[10005];

int v[2][10005];

int main() {
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; ++i){
        cin >> a[i].w >> a[i].p;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            if (j - a[i].w >= 0)
                v[i % 2][j] = max(v[(i - 1) % 2][j], v[(i - 1) % 2][j - a[i].w] + a[i].p);
            else
                v[i % 2][j] = v[(i - 1) % 2][j];
        }
    }

    cout << v[n % 2][k];

}