#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int dp[2][10001];
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)
            {
                if(dp[0][j]<dp[0][j-2]+p) dp[1][j]=dp[0][j-w]+p;
                else dp[1][j]=dp[0][j];
            }
            else dp[1][j]=dp[0][j];
        }
        memcpy(dp[0],dp[1],nr);
    }
    fout<<dp[1][g];
}