#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define dbg(x) cout << #x << ": " << x << "\n";
using ll = long long;

const string myf = "rucsac";
ifstream fin(myf + ".in");
ofstream fout(myf + ".out");

int dp[2][10005];
int n, g;
pair<int, int> a[5005];

int main()
{

    fin >> n >> g;
    for (int i = 1; i <= n; ++i)
        fin >> a[i].first >> a[i].second;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= g; j++)
            if (a[i].first > j)
                dp[i & 1][j] = dp[(i - 1) & 1][j];
            else
                dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - a[i].first] + a[i].second);
    fout << dp[n & 1][g] << '\n';
    fin.close();
    fout.close();
    return 0;
}