#include <fstream>
#include <vector>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n, G;
struct ob
{
    int w, p;
};
vector <ob> v;
int step, ans;
vector<vector<int>> dp;
int main()
{
    cin >> n >> G;

    v.resize(n+1);
    dp.assign(2, vector<int>(G+1, 0));
    for(int i=1; i<=n; i++)
        cin >> v[i].w >> v[i].p;
    for(int i=1; i<=n; i++, step=1-step)
    {
        dp[step].assign(G+1, 0);
        for(int j=0; j<=G; j++)
        {
            dp[step][j] = dp[1-step][j];
            if(j >= v[i].w && dp[1-step][j-v[i].w] + v[i].p > dp[step][j])
                dp[step][j] = dp[1-step][j-v[i].w] + v[i].p;

        }
    }
    step=1-step;
    for(int i=1; i<=G; i++)
        ans=max(ans, dp[step][i]);
    cout << ans;
    return 0;
}