#include <bits/stdc++.h>

using namespace std;

int n,g;
int dp[2][10005];
int W[1001],P[1001];

int main()
{
    freopen("rucsac.in" , "r" , stdin);
    freopen("rucsac.out" , "w" ,stdout);
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin >> n >> g;
    int l = 0;
    for(int i = 1;i <= n; ++i)
        cin >> W[i] >> P[i];
    for(int i = 1;i <= n; ++i,l ^= 1){
        for(int j = 1;j <= g; ++j){
            dp[1-l][j] = dp[l][j];
            if(j >= W[i]){
                dp[1-l][j] = max(dp[1-l][j],dp[l][j-W[i]]+P[i]);
            }
        }
    }
    cout << dp[l][g];
}
/**

**/