#include <bits/stdc++.h>
#define cin ci
#define cout co
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
const int Nmax = 5e3 + 1;
int n , g;
vector<pair<int, int>> ob;
vector<int> dp;
int main()
{
    cin >> n >> g;
    dp.resize(g + 1, 0);
    ob.assign(n + 1, {0, 0});
    for(int i = 1; i <= n; i++)
        cin >> ob[i].first >> ob[i].second;
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = g - ob[i].first; j >=0; j--)
            if(dp[j])
                dp[j + ob[i].first] = max(dp[j + ob[i].first], dp[j] + ob[i].second);
    int maxi = -1;
    for(int i = 1; i <= g; i++)
        maxi = max(maxi, dp[i]);
    cout << maxi - 1;

    return 0;
}