#include <bits/stdc++.h>
using namespace std;
#define mod                1000000007
#define ll                 long long 
#define all(v)             v.begin(), v.end()
#define fr(n)              for(ll i=0;i<n;++i)
#define ctz(x)             __builtin_ctzll(x)
#define clz(x)             __builtin_clzll(x)
#define pcount(x)          __builtin_popcountll(x)
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
// #define cin fin
// #define cout fout
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");



void solve(){
    ll n, m;cin>>n>>m;
    // ll dp[n+1][m+1];
    // memset(dp, 0, sizeof dp);
    // fr(n){
    //     for(ll j=0; j<m;j++){
    //         cout<<dp[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    vector<ll> v(m+1, 0);
    // fr(m) cout<<v[i]<<" ";
    for(ll i=1; i<=n; i++){
        ll a, b; cin>>a>>b;
        // v.push_back(make_pair(a, b));
        vector<ll> v2(m+1, 0);
        for(ll j=1; j<=m; j++){
            if(j<a) v2[j]=v[j];
            else{
                v2[j]=max(v[j], v[j-a]+b);
            }
        }
        v=v2;
        // fr(m+1) cout<<v[i]<<" ";
        // cout<<"\n";
    }
    cout<<v[m];
}


int main(){
//    ios_base::sync_with_stdio(false); cin.tie(NULL);
//    ll t;cin>>t;while(t--){solve();cout<<endl;}
    solve();
}