#include <fstream>
#include <cstring>

using namespace std;

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

int N, G, MAX, a[10003], p[5003], w[5003];
int main()
{
    f >> N >> G;
    memset(a, -1, sizeof(a));
    a[MAX] = 0;
    for(int i = 1; i <= N; i++) f >> w[i] >> p[i];
    for(int i = 1; i <= N; i++) {
        for(int j = MAX; j >= 0; j--) {
            if(a[j] != -1 && j + w[i] <= G && a[j] + p[i] > a[j + w[i]])
                a[j + w[i]] = a[j] + p[i], MAX = max(MAX, j + w[i]);
        }
    }
    MAX = 0;
    for(int i = 1; i <= G; i++) MAX = max(MAX, a[i]);
    g << MAX << "\n";
    return 0;
}