#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, G;
int c[5005], g[5005], dp[2][10005];
int main()
{
    int i, j, mx = 0, l1, l2;
    fin >> n >> G;
    for(i = 1; i <= n; i++)
        fin >> g[i] >> c[i];
    l1 = 0;
    l2 = 1;
    dp[l1][g[1]] = c[1];
    dp[l1][0]= 0;

    for(i = 2; i <= n; i++)
    {
        for(j = 0; j <= G; j++)
            if(j >= g[i])
                dp[l2][j] = max(dp[l1][j - g[i]] + c[i], dp[l1][j]);
            else dp[l2][j] = dp[l1][j];
        swap(l1, l2);
    }
    for(i = 0; i <= G; i++)
        mx = max(mx, dp[l1][i]);
    fout << mx;
    return 0;
}