#include <bits/stdc++.h>
using namespace std;

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

int weights[10001]; // G + 1

int main() {
    
    int i, j;
    int N, G;
    f>>N>>G;
    int p[10001], w[10001];

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

    for (i = 0; i < N; i++)
        for (j = G; j >= w[i]; j--)
            weights[j] = max(weights[j], p[i] + weights[j - w[i]]);

    g<<weights[G];

    return 0;
}