#include <bits/stdc++.h>
#define mod 104659

using namespace std;

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

int n, G;
int v[5005], g[5005];
int dp[10005];

int main()
{
    int i, j, maxim;
    fin >> n >> G;
    for(i = 1; i <= n; i++)
        fin >> g[i] >> v[i];
    for(i = 1; i <= n; i++)
        for(j = G; j >= g[i]; j--)
            dp[j] = max(dp[j], dp[j - g[i]] + v[i]);
    maxim = 0;
    for(i = 1; i <= G; i++) maxim = max(maxim, dp[i]);
    fout << maxim << '\n';
    return 0;
}