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

class Obiect {
    public:
        int w, p;
        friend istream &operator>>(istream &, Obiect &);
};

istream &operator>>(istream &in, Obiect &obj) {
    in >> obj.w >> obj.p;
    return in;
}

Obiect *read(int &n, int &G) {
    ifstream fin("rucsac.in");
    if (!fin.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    fin >> n >> G;
    Obiect *v = new Obiect[n + 1];
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }

    fin.close();

    return v;
}



int main() {
    int n, G;
    Obiect *v = read(n, G);

    int **cost = new int*[n + 1];
    for (int i = 0; i <= n; ++i) {
        cost[i] = new int[G + 1];
        for (int j = 0; j <= G; ++j)
            cost[i][j] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        for (int gr = 1; gr <= G; ++gr) {
            if (v[i].w <= gr) {
                cost[i][gr] = max(cost[i - 1][gr], cost[i - 1][gr - v[i].w] + v[i].p);
            }
        }
    }

    ofstream fout("rucsac.out");
    fout << cost[n][G] << '\n';
    free(v);

    return 0;
}