#include <fstream>
#include <algorithm>

using namespace std;

const char *INPUT_FILE_PATH = "rucsac.in";
const char *OUTPUT_FILE_PATH = "rucsac.out";

int main() {
    ifstream cin(INPUT_FILE_PATH);
    ofstream cout(OUTPUT_FILE_PATH);
    int n, g;
    cin >> n >> g;
    int *dp = new int[g + 1];
    fill(dp, dp + g + 1, 0);
    while (n--) {
        int weight, value;
        cin >> weight >> value;
        for (int tempWeight = g; tempWeight >= weight; --tempWeight) {
            dp[tempWeight] = max(dp[tempWeight], dp[tempWeight - weight] + value);
        }
    }
    cout << *max_element(dp, dp + g + 1);
    return 0;
}