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

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

const int nmax = 5005;
const int wmax = 10005;

int dp[nmax][wmax];

struct object {
    int weight;
    int value;
};

int main() {

    int N, maxWeight;
    fin >> N >> maxWeight;
    vector<object> objects(N + 1);

    for(int i = 1; i <= N; ++i) {
        fin >> objects[i].weight;
        fin >> objects[i].value;
    }
    vector<int> maxProfit(maxWeight + 5, 0);
    for(int i = 1; i <= N; ++i)
        for(int j = maxWeight; j >= objects[i].weight; --j) {
                maxProfit[j] = max(maxProfit[j], maxProfit[j - objects[i].weight] + objects[i].value);
        }

                /*dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - objects[i].weight] + objects[i].value);
            else dp[i][j] = dp[i - 1][j];*/

    fout << maxProfit[maxWeight] << '\n';



    return 0;
}