#include <fstream>
#include <climits>
using namespace std;

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

const int mxN = 5001, mxG = 10001;
int greu[mxN], prof[mxN];
int dp[mxG];
int n, G;

int main() {
    fin >> n >> G;
    for (int i = 1; i <= n; i++)
        fin >> greu[i] >> prof[i];

    for (int i = 1; i <= G; i++)
        dp[i] = INT_MIN;
    dp[0] = 0;

    for (int i = 1; i <= n; i++)
        for (int g = G; g >= greu[i]; g--)
            if (dp[g - greu[i]] != INT_MIN)
                if (dp[g - greu[i]] + prof[i] > dp[g])
                    dp[g] = dp[g - greu[i]] + prof[i];

    int ans = 0;
    for (int g = 0; g <= G; g++)
        if (dp[g] != INT_MIN && dp[g] > ans)
            ans = dp[g];

    fout << ans << "\n";
    return 0;
}