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

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int g[5001], p[5001], freq[10001], i, j, N, G;

int main() {
    fin >> N >> G;
    for(i = 0; i < N; i++) {
        fin >> g[i] >> p[i];
        for(j = G; j > 0; j--) {
            if(freq[j] != 0) {
                if(j + g[i] <= G) {
                    if(freq[j + g[i]] < p[i] + freq[j]) {
                        freq[j + g[i]] = p[i] + freq[j];
                    }
                }
            }
            if(j == g[i]) {
                if(freq[j] < p[i]) {
                    freq[j] = p[i];
                }
            }
        }
    }
    for(i = G; i > 0; i--) {
        if(freq[i] != 0) {
            fout << freq[i] << ' ';
            break;
        }
    }
    fin.close();
    fout.close();
    return 0;
}