#include <fstream>
//#define DEBUG
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n, w[1000], W, j, i, m[1000][1000], v[100];
int main()
{
    cin>>n;
    cin>>W;
    for(i=1;i<=n;i++)
       cin>>w[i]>>v[i];
    for(i=0;i<=W;i++)
       m[0][i]=0;
    for (i=1;i<=n;++i)
        for (j=1;j<=W;++j)
            if (j >= w[i])
                    m[i][j] = max(m[i-1][j], m[i-1][j-w[i]] + v[i]);
            else
                    m[i][j] = m[i-1][j];
  #ifdef DEBUG
    for(i=1;i<=n;i++)
     {for(j=1;j<=W;++j)
        cout<<m[i][j]<<" ";

    cout<<"\n";}
  #endif
    cout<<m[n][W];
    return 0;
}