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

int rucsac(int v[], int g[], int n, int G) {
    int dp[G + 1] = {0};

    for(int i = 0; i < n; i++)
        for (int j = G; j >= g[i]; j--)
            dp[j] = max(dp[j], dp[j - g[i]] + v[i]);
    return dp[G];
}

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int n, G;
    int v[5001], g[5001];

    fin >> n >> G;
    for(int i = 0; i < n; i++)
        fin >> g[i] >> v[i];
    fout << rucsac(v, g, n, G);
}