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


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

    int n, max_weight;

    fin >> n >> max_weight;

    vector<vector<int>> dp(3, vector<int>(max_weight + 1, 0));

    for (int i = 1; i <= n; i++) {
        int weight, price;

        fin >> weight >> price;
        for (int j = 0; j <= max_weight; j++) {
            if (j < weight) {
                dp[2][j] = dp[1][j];
            } else {
                dp[2][j] = max(dp[1][j], dp[1][j - weight] + price);
            }
        }
        dp[1] = dp[2];
    }

    fout << dp[1][max_weight];

    fout.close();
    fin.close();
}