#include<bits/stdc++.h>
using namespace std;
int C[5010],P[5010],DP1[10010],DP2[10010];
int N,G;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int main()
{
    in>>N>>G;
    for(int i = 1; i <= N; i++)
        in>>C[i]>>P[i];
    for(int i = 1; i <= N; i++)
    {
       for(int j = 1; j <= G; j++)
        {
            DP2[j] = DP1[j];
            if (C[i] <= j)
                DP2[j] = max(DP2[j] , DP1[j - C[i] ] + P[i]);
        }
        for(int j = 1; j <= G; j++)
            DP1[j] = DP2[j];
    }
    out<<DP2[G];
    return 0;
}