#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

const string filename = "rucsac";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

int n, cap, g[5005], p[5005], dp[10005], d[10005];

int main()
{
    fin >> n >> cap;
    for(int i = 1; i <= n; i++)
        fin >> g[i] >> p[i];
    for(int i = 1; i <= n; i++)
    {
        for(int j = g[i]; j <= cap; j++)
            d[j] = max(dp[j], dp[j - g[i]] + p[i]);
        for(int j = 0; j <= cap; j++)
            dp[j] = d[j];
    }
    int ans = -1;
    for(int j = 0; j <= cap; j++)
        ans = max(ans, dp[j]);
    fout << ans << '\n';
    return 0;
}