#include <iostream>
#include <fstream>

using namespace std;
const int GMAX = 10000;

int d[GMAX + 5];


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

    int n, m, g, p, maxim, ans;
    fin >> n >> m;
    d[0] = 1;
    maxim = ans = 0;
    for (int nr = 1; nr <= n; ++nr) {
        fin >> g >> p;
        for (int i = min(maxim, m - g); i >= 0; --i) {
            if (d[i] != 0) {
                if (d[i + g] < d[i] + p) {
                    d[i + g] = d[i] + p;
                    if (d[i] + p > ans) {
                        ans = d[i] + p;
                    }
                }
            }
        }
        maxim += g;
        if (maxim > m) {
            maxim = m;
        }
    }
    fout << ans - 1;
    return 0;
}