#include <iostream>
#include <fstream>
#define nmax 5005
using namespace std;
unsigned long long n,mx,i,w[nmax],v[nmax],dp[nmax][10005],j;
int main()
{
    ifstream f ("rucsac.in");
    ofstream g ("rucsac.out");
f>>n>>mx;
for (i=1;i<=n;i++) f>>w[i]>>v[i];
for (i=0;i<=n;i++)
    for (j=0;j<=mx;j++)
    {
    if (i==0 || j==0) dp[i][j]=0;
    else
    {
        if (w[i]>j) dp[i][j]=dp[i-1][j];
        else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
    }
    }
g<<dp[n][mx];
}