#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("-O3")
#define ll long long  int
// #include <boost/multiprecision/cpp_int.hpp>
// using boost::multiprecision::cpp_int;
// cpp_int x;
// namespace mp=boost::multiprecision;
// mp::cpp_int s=n;
#define all(x) (x).begin(), (x).end()
using ld = long double;
const ll mod = 1000000007;
const ll inf = 1000000000000000000;
const ll rk = 256;
const ld PI = 3.141592653589793;
#define pb push_back
#define mp make_pair
#define vc vector
#define fs first
#define sec second
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pll pair<ll,ll>
#define pls pair<ll,string>
#define psl pair<string,ll>
#define plc pair<ll,char>
#define pcl pair<char,ll>
#define pss pair<string,string>
#define all(x) (x).begin(), (x).end()
#define tol(s) transform(s.begin(),s.end(),s.begin(),::tolower);
#define tou(s) transform(s.begin(),s.end(),s.begin(),::toupper);
#define print(a) for(auto j:a) {cout<<j<<",";} cout << "\n";
#define endl '\n'
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
// getting string line
// getline(cin,word);

// STL:
//        (1) PRIORITY_QUEUE pq:
//        -> priority_queue < int > pq; // max_heap
//        -> priority_queue < int , vector < int > , greater < int > > pq; // min_heap
//        -> pq.top()   --> returns the maximum or minimum element
//        -> pq.push()  --> push element into the queue
//        -> pq.pop()   --> remove top most element
//        -> pq.empty() --> checks whether queue is empty or not

//        (2) set / multiset  ss;
//        --> ss.insert(key); (insertion)
//        --> ss.erase(ss.find(key)) .. (deletion)
//        --> ss.find(key) != ss.end() ..existence check
//        --> ss.lower_bound(x) -> smallest value which is greater than or equals to x
//        --> ss.upper_bound(x) --> first value strictly greater than x
//        --> multiset< data_type , greater<data_type> > ms; // for max ordering

//        (3) common functions
//        lower_bound(v.begin(),v.end(),x) - v.begin() --> smallest value greater than or equals to x
//        upper_bound(v.begin(), v.end(),x)- v.begin() --> smallest value greater than x
//        memset(dp , val , sizeof(dp)) -> sets the value of array dp to val

//        (4)  common mistakes
//            .) long long vs int overflow
//            .) read question carefully please!!!! it can cost you a lot
//            .) unorderedmap is O(1) look up but worst case can be bad
//            .) maps have higher constant so many lookups can cause TLE
//            .) leaving debugs or cerrs in the program at times can cause TLE


// // Printing pair
ostream & operator << (ostream & os, pair <ll, ll> const& x) {
    os << x.first << "," << x.second;
    return os;
}

// printing vector
template <class T>
ostream & operator << (ostream & os, vector <T> const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

// printing set
template <class T>
ostream & operator << (ostream & os, set <T> const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
    return os << "[ " << p.first << ", " << p.second << "]" ;
}

bool sortinrev(const pair<ll,ll> &a,const pair<ll,ll> &b){
    return (a.first > b.first);
}


ll modularexpo(ll x,ll n,ll mod){
    ll res = 1;
    while(n>0){
        if(n%2==1)
            res = (res*x)%mod;
        x = (x*x)%mod;
        n = n/2;
    }
    return res;
}

void primegen(ll n){
    for(ll i=1;i<=sqrt(n);i++){
        if(n%i==0){
            if(n/i==i)
                cout<<i<<endl;
                // prime.pb(i);
            else{
                cout<<i<<" "<<n/i<<endl;
                // prime.pb(i);
                // prime.pb(n/i);
            }
        }
    }
}

bool primetest(ll n){
    if(n==1)
        return false;
    else{
        for(ll i=2;i*i<=n;i++){
            if(n%i==0)
                return false;
        }
        return true;
    }
}


ll phi(ll n){
    ll res = n;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0){
            res = res/i;
            res = res*(i-1);
            while(n%i==0){
                n = n/i;
            }
        }   
    }
    if(n>1){
        res = res/n;
        res = res*(n-1);
    }
    return res;
}


vc<ll> temp;
void divisors(ll n){
    for(ll i=1;i<=sqrt(n);i++){
        if(n%i==0){
            if(n/i==i)
                temp.pb(i);
            else{
                temp.pb(i);
                temp.pb(n/i);
            }
        }
    }
}

struct Triplet{
    ll x,y,z;
};

string bits(ll n){
    int arr[100];
    int i = 0; 
    while (n > 0){
        arr[i] = n % 2; 
        n = n / 2; 
        i++; 
    }
    string s="";
    for (int j = i-1; j >= 0; j--){
        if(arr[j]==1)
            s+='1';
        else
            s+='0';
    }
    return s;
}

int main(){
    FastIO;
    ll n,wt;
    cin>>n>>wt;
    vc<pair<ll,ll>> arr;
    for(ll i=0;i<n;i++){
        ll x,y;
        cin>>x>>y;
        arr.pb(mp(x,y));
    }
    ll dp[n+1][wt+1];
    memset(dp,0,sizeof(dp));
    for(ll i=1;i<n+1;i++){
        ll w = arr[i-1].first;
        ll val = arr[i-1].second;
        for(ll j=1;j<wt+1;j++){
            if(j<w)
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+val);
        }
    }
    cout<<dp[n][wt]<<endl;
    return 0;
}



Measured memory_bytes: 79232