#include <bits/stdc++.h>

using namespace std;

#define w first
#define p second

pair<int, int> obj[5005];
int dp[10005];

int main()
{
    ifstream fin("rucsac.in");
    ofstream fout("rucsac.out");
    int n, G;
    fin >> n >> G;
    for(int i = 1; i <= n; ++i)
        fin >> obj[i].w >> obj[i].p;
    for(int i = 1; i <= G; ++i) dp[i] = -1e9;
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        for(int j = G; j >= obj[i].w; --j){
            dp[j] = max(dp[j], dp[j - obj[i].w] + obj[i].p);
            ans = max(ans, dp[j]);
        }
    }
    fout << ans;
    return 0;
}