#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, g;
int dp[2][10005];
pair<int, int>a[5005];
int main()
{
    int i, j, l;
    fin >> n >> g;
    for(i = 1;i <= n;i++)
        fin >> a[i].first >> a[i].second;
    dp[1][a[1].first] = a[1].second;
    for(i = 1, l = 1;i <= n;i++, l = 1 - l)
        for(j = 1;j <= g;j++)
        {
            dp[l][j] = dp[1 - l][j];
            if(j >= a[i].first)
                dp[l][j] = max(dp[l][j],
                           dp[1 - l][j - a[i].first] + a[i].second);
        }
    fout << dp[1 - l][g] << "\n";
    return 0;
}