#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int main()
{
    int n, g, w[10000], p[10000], profit = 0;
    in >> n >> g;
    for (int i = 1; i <= n; i++)
        in >> w[i] >> p[i];

    int dp[n + 1][g + 1];

    for (int i = 1; i <= g; i++)
        dp[0][i] = i;

    for (int i = 1; i <= n; i++)
        dp[i][0] = i;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= g; j++)
            if (w[i] <= j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]);
            else
                dp[i][j] = dp[i - 1][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= g; j++)
            profit = max(profit, dp[i][j]);
    
    out << profit;
    return 0;
}