#include <iostream>
#include <fstream>

using namespace std;

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

int n,m,i,j;
int w[5086],v[5086];
int dp[2][5086];
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>w[i]>>v[i];
    int p=0;
    for(i=1;i<=n;i++,p=1-p)
        for(int g=0;g<=m;g++)
        {
            dp[1-p][g] = dp[p][g];
            if(g>=w[i]){
                dp[1-p][g] = max(dp[1-p][g],dp[p][g-w[i]]+v[i]);
            }
        }
    g<<dp[p][m];
}