#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int dp[4][10001];
int n, k, g, s;
int main()
{
    fin>>n>>k;
    fin>>g>>s;
    for(int i=g;i<=k;i++)
        dp[2][i]=s;

    for(int i=2;i<=n;i++)
    {
        fin>>g>>s;
        for(int j=1;j<=k;j++)
        if(j>=g)
                    dp[i%2+1][j]=max(dp[(i-1)%2+1][j],s+dp[(i-1)%2+1][j-g]);
        else dp[i%2+1][j]=dp[(i-1)%2+1][j];
    }
    fout<<dp[n%2+1][k];
    return 0;
}