#include <fstream>
using namespace std;
int dp[2][10001];
int W[5001],P[5001];
int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    int n,g;
    cin>>n>>g;
    for(int i=1;i<=n;i++)
    {
        cin>>W[i]>>P[i];
        for(int j=W[i];j<=g;j++)
            dp[2][j]=max(dp[2][j],dp[1][j-W[i]]+P[i]);
        for(int j=0;j<=g;j++)
            dp[1][j]=dp[2][j];
    }
    cout<<dp[2][g];
    return 0;
}