#include <bits/stdc++.h>
using namespace std;
int dp[10002], v[5002], p[5002];

int main(void){
    ofstream cout("rucsac.out");
    ifstream cin("rucsac.in");
    int n , G;
    cin >> n >> G;
    for(int i = 1;i<=n;i++)cin >> v[i] >> p[i];
    dp[0] = 0;
    for(int i = 1;i<=G;i++){
        dp[i] = -1;
    }
    int maxindice = 0;
    for(int i = 1;i<=n;i++){
        for(int j = maxindice;j>=0;j--){
            if(dp[j] != -1 && j + v[i] <= G && dp[j + v[i]] < dp[j] + p[i]){
                dp[j + v[i]] = dp[j] + p[i];
                maxindice = max(maxindice, j + v[i]);
            }
        }
    }
    int sol = 0;
    for(int i = 1;i<=G;++i)sol = max(sol, dp[i]);
    cout << sol;
}