#include <bits/stdc++.h>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int DP[5001][10001]={0};
int W[5001],P[5001];
int N,G;

int main()
{
    f>>N>>G;
    for(int i=1;i<=N;i++)
    {
        int w,p;
        f>>w>>p;
        W[i]=w;
        P[i]=p;
    }

    for(int i=1;i<=N;i++)
        for(int j=W[i];j<=G;j++)
            DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+P[i]);

    g<<DP[N][G];

}