#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int dp[2][10001];
inline int maxi(int a,int b)
{
    if(a>b) return a;
    return b;
}
int main()
{
    int n,g,i,w,j,p;
    fin>>n>>g;
    int nr=sizeof(dp[1]);
    for(i=1;i<=n;++i)
    {
        fin>>w>>p;
        for(j=0;j<=g;++j)
        {
            if(j>=w)
            {
                dp[1][j]=maxi(dp[0][j],dp[0][j-w]+p);
            }
            else dp[1][j]=dp[0][j];
        }
        memcpy(dp[0],dp[1],nr);
    }
    fout<<dp[1][g];
}