#include <fstream>
#define G first
#define c second

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,k,j,i,l,L;
pair <int,int> v[5005];
int dp[3][10005];
int main()
{
    f>>n>>k;
    for(i=1;i<=n;i++)
    {
        f>>v[i].G>>v[i].c;
    }
    for(i=1;i<=n;i++)
    {
        L=l;
        if(l==1)
            l=2;
        else
            l=1;
        for(j=0;j<=k;j++)
        {
            dp[l][j]=dp[L][j];
            if(j>=v[i].G)
                dp[l][j]=max(dp[l][j],dp[L][j-v[i].G]+v[i].c);
        }
    }
    g<<dp[l][k]<<'\n';
    return 0;
}