#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 fin("rucsac.in");
ofstream fout("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";
    // }
    for(ll i=1; i<=n; i++){
        ll a, b; cin>>a>>b;
        // v.push_back(make_pair(a, b));
        for(ll j=1; j<=m; j++){
            if(j<a) dp[i][j]=dp[i-1][j];
            else{
                dp[i][j]=max(dp[i-1][j], dp[i-1][j-a]+b);
            }
        }
    }
    cout<<dp[n][m];
}


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