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

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