#include <iostream>
//#include <bits/stdc++.h>
#include <cstdio>
#include <list>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <limits.h>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <utility>
#define all(x) (x).begin(), (x).end() 
#define ull unsigned long long int
#define ll long long int 
#define ld long double
#define pb push_back
#define ep emplace_back
#define mp make_pair
#define pcc pair<char,char>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue <ll> 
#define ppq priority_queue <pll>
#define vi vector <int>
#define vb vector <bool>
#define vl vector <ll>
#define vpl vector <pll>
#define vc vector <char>
#define mmi multimap<int,int>
#define mml multimap<ll,ll>
#define mmc multimap<char,char>
#define mi map<int,int>
#define ml map<ll,ll>
#define mc map<char,char>
#define clr(a) memset(a,0,sizeof(a))
#define mod 1000000007
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define endl "\n"
#define INF 1e+18
using namespace std;
bool primecheck(ll a)
{
    bool check  = true;

    for(ll i=2;i<=sqrt(a);i++)
    {
        if(a%i==0){
            check = false;
            break;
        }
    }

    return(check);
}
vl printDivisors(ll n) 
{ 
    // Note that this loop runs till square root 
    vl sol;
    for (ll i=1; i<=sqrt(n); i++) 
    { 
        if (n%i == 0) 
        { 
            // If divisors are equal, print only one 
            if (n/i == i){ 
                //printf("%d ", i);
               sol.pb(i); 
                 }
  
            else {
                sol.pb(i);
                sol.pb(n/i);
            }// Otherwise print both 
                //printf("%d %d ", i, n/i); 
        } 
    } 
    return(sol);
} 
ll digits(ll a)
{
    return(floor(log10(a))+1);
}
ll bits(ll a)
{
    return(floor(log2(a))+1);
}
long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int gcd(int a, int b) 
{ 
    // Everything divides 0  
    if (a == 0) 
       return b; 
    if (b == 0) 
       return a; 
   
    // base case 
    if (a == b) 
        return a; 
   
    // a is greater 
    if (a > b) 
        return gcd(a-b, b); 
    return gcd(a, b-a); 
}
ll lcm(ll a, ll b)  
 {  
    return (a*b)/gcd(a, b);  
 }
 void addEdge(vl adj[],ll u, ll v)
 {
    adj[u].pb(v);
    adj[v].pb(u);
 }
 vl path;
 void dfs(ll u, vl adj[], vb &visited, ll parent = -1)
 {
    visited[u] = true;
    path[u] = parent;
    // count<<u<<endl;
    for(ll i=0;i<adj[u].size();i++)
    {
        if(visited[adj[u][i]]==false)
        {
            dfs(adj[u][i],adj,visited,u);
        }
    }
 }
 /*
unique(all(vec)); will remove all duplicate elements from the vector
 */

vector<vl> dp(101,vl(100001,-1));

ll knapsack(ll cap,ll pos, vl weights, vl price)
{
    //cout<<cap<<" "<<pos<<endl;
    if(cap==0 || pos==-1)
        return 0;
    if(pos==0)
    {
        if(weights[pos]>cap)
            return 0;
        else
            return(price[pos]);
    }

    if(weights[pos]>cap){
        if(dp[pos-1][cap] ==-1){
            dp[pos-1][cap] = knapsack(cap,pos-1,weights,price);
            
        }
        
        
        return dp[pos-1][cap];
    }

    if(dp[pos-1][cap-weights[pos]]==-1)
    {
        dp[pos-1][cap-weights[pos]] = knapsack(cap-weights[pos],pos-1,weights,price);
    }
    

    if(dp[pos-1][cap]==-1)
    {
        dp[pos-1][cap] = knapsack(cap,pos-1,weights,price);
    }
   

    dp[pos][cap] = max(price[pos]+dp[pos-1][cap-weights[pos]],dp[pos-1][cap]);

    return(dp[pos][cap]);

}
int main()
{
    fastio;

    ll a,b,c,i,j,k,l,m,n,t;

    ll cap;

    cin>>a>>cap;

    vl weights, price;

    



    for(i=0;i<a;i++)
    {
        cin>>m>>n;
        weights.pb(m);
        price.pb(n);
        //cin>>weights[i]>>price[i];
    }

    // for(i=0;i<a;i++)
    // {
    //     for(j=0;j<cap;j++)
    //         cout<<dp[i][j]<<" ";
    //     cout<<endl;
    // }

    cout<<knapsack(cap,a-1,weights,price)<<endl;

    
}

Measured memory_bytes: 80256