#include <bits/stdc++.h>
#define nmax 5001
#define gmax 10001

using namespace std;

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

short dp[nmax][gmax],n,G,g[nmax],v[nmax];

int main()
{
    short i,j;
    fin >> n >> G;
    for(i = 1; i <= n; i++)
        fin >> g[i] >> v[i];

    for(i = 1; i <= n; i++)
        for(j = 1; j <= G; j++)
            if(g[i] > j) dp[i][j] = dp[i-1][j];
            else
            {
                if(dp[i-1][j] > dp[i-1][j-g[i]] + v[i])
                    dp[i][j] = dp[i-1][j];
                else dp[i][j] = dp[i-1][j-g[i]]+v[i];
            }

    fout << dp[n][G] << "\n";

    fin.close();
    fout.close();
    return 0;
}