(0,1) KnapSack

#include<bits/stdc++.h>
using namespace std;
typedef long long   ll;
typedef pair<ll,ll> pll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL))
#define fi first
#define se second
#define pb push_back
ll const MOD=1000000007;
#define eb emplace_back
const int N=10000005;

int main()
{

   ll n,m;

   cin>>n>>m;


   ll p[n+1],wt[n+1];

   p[0]=wt[0]=0;


   for(ll i=1;i<=n;i++)
   {
       cin>>wt[i]>>p[i];

   }


   ll dp[n+1][m+1];

   for(ll i=0;i<=n;i++)
   {

       for(ll w=0;w<=m;w++)
       {
           if(i==0 || w==0)dp[i][w]=0;

           else if(wt[i]<=w)
           {

               dp[i][w]=max(p[i]+dp[i-1][w-wt[i]],dp[i-1][w]);


           }else dp[i][w]=dp[i-1][w];



       }


   }

   cout<<dp[n][m]<<endl;





}