#include <bits/stdc++.h>
using namespace std;
ifstream fcin("rucsac.in");
ofstream fcout("rucsac.out");
typedef long long ll;
typedef long double ld;


const int N = 5e3 + 5;
int dp[2][10005], n, G, g[N], v[N], rasp, l0, l1;

/**
dp[i][j] = profitul maxim obtinut din primele i obiecte si avand
           greutatea j
dp[1][0] = 0
dp[1][g[1]] = v[1]
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - g[i]] + v[i])
*/

int main()
{
    fcin >> n >> G;
    for (int i = 1; i <= n; i++)
        fcin >> g[i] >> v[i];
    l1 = 1;
    dp[l0][g[1]] = v[1];
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= G; j++)
        {
            int maxx = dp[l0][j];
            if (j >= g[i])
                maxx = max(maxx, dp[l0][j - g[i]] + v[i]);
            dp[l1][j] = maxx;
        }
        swap(l0, l1);
    }
    for (int i = 1; i <= G; i++)
        rasp = max(rasp, dp[l0][i]);
    fcout << rasp;
    fcin.close();
    fcout.close();
    return 0;
}