//Jacker0031
//packages
#if __has_include("extra.cpp") && __has_include(<stdint.h>)
    #include "extra.cpp"
#else
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <utility>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <cassert>
using namespace std;
#endif

// Data Type
#define ull                 unsigned long long int
#define ll                  long long int
#define ld                  long double
// Loops
#define loop(i,s,e)         for(ll i=(s); i<(e); i++)
#define rloop(i,s,e)        for(ll i=(s); i>=(e); i--)
#define iter(it,var)        for(auto it=var.begin(); it!=var.end(); it++)
#define riter(it,var)       for(auto it=var.rbegin(); it!=var.rend(); it++)
// Stl
#define pb                  push_back
#define pf                  push_front
#define eb                  emplace_back
#define popb                pop_back
#define popf                pop_front
#define mp                  make_pair
#define mt                  make_tuple
#define ff                  first
#define ss                  second
#define vll                 vector<ll>
#define vvl                 vector<vll>
#define pll                 pair<ll,ll>
#define mll                 map<ll,ll>
#define ub                  upper_bound                
#define lb                  lower_bound
#define bs                  binary_search        
#define all(x)              x.begin(),x.end()
#define rall(x)             x.rbegin(),x.rend()
#define get(tup,ind)        get<ind>(tup)
// Maths
const double PI = 2*acos(0.0);
#define gcd(a,b)            __gcd((a),(b))
#define lcm(a,b)            ((a)/(__gcd((a),(b)))*(b))
#define log(x,b)            (log(x)/log(b))
#define INF                 LLONG_MAX
// Big data
const int Mod = 1E9 + 7;
#define Mul(a,b)            (((a) % Mod)*((b) % Mod)) % Mod
#define Sum(a,b)            (((a) % Mod)+((b) % Mod)) % Mod
#define Sub(a,b)            (((a) % Mod)-((b) % Mod) + Mod) % Mod
#define Div(a,b)            Mul(a,modInverse(b))
// Extra
#define fast                ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define scan(any)           for(auto &i:any) cin>>i;
#define print(any)          {for(auto &i:any) cout<<i<<" "; nl;}
#define printp(any)         for(auto &i:any) cout<<i.ff<<" "<<i.ss<<endl;
inline void yes()           {std::cout<<"Yes\n";}
inline void no()            {std::cout<<"No\n";}
#define flush               std::cout.flush()
#define nl                  std::cout<<'\n'
#define endl                '\n'    
using namespace std;
ll isPrime(ll num){
    ll flag=0;
    for(ll i = 1; i <=num; i++) {
       if(num % i == 0) {
          flag++;
          if(flag>3)
              break;

       }
    }
    if(flag==3)
        return 1;
    else
        return 0;

}
ll binomialCoeff(ll n, ll k) 
{ 
    ll C[k+1]; 
    memset(C, 0, sizeof(C)); 
  
    C[0] = 1;  // nC0 is 1 
  
    for (ll i = 1; i <= n; i++) 
    { 
        for (ll j = min(i, k); j > 0; j--) 
            C[j] = C[j] + C[j-1]; 
    } 
    return C[k]; 
} 
ll factorial(ll n) 
{ 
    if (n == 0) 
        return 1; 
    return n * factorial(n - 1); 
} 


bool isPalindrome(string str) 
{ 
    int l = 0; 
    int h = str.length() - 1; 
    while (h > l) 
    { 
        if (str[l++] != str[h--]) 
        { 
            
            return false; 
        } 
    } 
    return true; 
} 



/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

//NOW CODE BEGIN.
//DHARMSINH DESAI UNIVERSITY.
bool check(long long int n)
{
    double y=sqrt(n);
    if(y-floor(y)==0)
    return 1;
    else
    return 0;
}
bool isprime(long long int N){
    if(N<2 || (!(N&1) && N!=2))
        return 0;
    for(int i=3; i*i<=N; i+=2){
        if(!(N%i))
            return 0;
    }
    return 1;
}

int main()
{
     ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Jenish
    freopen("C:/Sublime Text 3/in.txt","r",stdin);
    freopen("C:/Sublime Text 3/out.txt","w",stdout);
    #endif
    ll x,y,cnt=0,l,o,t,n,sum=0,lasum=0,ans=0,las=0,flag=0,ma=INF,av1,av2,sum1=0,sum2=0;

    ll i,j,k,w,v,w1,W;
    cin>>n>>W;
    vll dp(W+1,0);
    loop(i,0,n)
    {
        cin>>w>>v;
        for(j=W-w;j>=0;j--)
        {
            dp[j+w]=max(dp[j+w],dp[j]+v);
        }
    }
    ll answer=0;
    for(i=0;i<=W;i++)
        answer=max(answer,dp[i]); 
    cout<<answer;
}   

Measured memory_bytes: 1024