#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,k,j,i,l,L;
struct idk
{
    int G,c;
}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;
}