#include <bits/stdc++.h>
using namespace std; 
typedef long long int ll;
#define mod 1000000007
ll gcd (ll a, ll b) {return ( a ? gcd(b%a, a) : b );}
ll modPow(ll x,ll n,ll MOD){ll res=1;while(n>0){if(n%2 == 1){res=(res*x)%MOD;}n/=2;x=(x*x)%MOD;}return res;}
ll modInverse(ll a,ll p){return modPow(a,p-2,p);}

void solve(ll wt[],ll val[],ll n,ll W)
{
    int i, j;
   ll K[n+1][W+1];
 
   for (i = 0; i <= n; i++)
   {
       for (j = 0; j <= W; j++)
       {
           if (i==0 || j==0)
               K[i][j] = 0;
           else if (j-wt[i-1]>=0)
                 K[ i ][ j ] = max(val[i-1] + K[i-1][j-wt[i-1]],  K[i-1][j]);
           else
                 K[ i ][ j ] = K[i-1][ j ];
       }
   }
 cout<< K[n][W];

}


int main()
{
     
   ios_base::sync_with_stdio (false);
   ll n,m,i,j,k;
   cin>>n>>m;
   ll wt[n],cost[n];
   
   for(i=0;i<n;i++)
   cin>>wt[i]>>cost[i];
   
   solve(wt,cost,n,m);
      
}