#include <bits/stdc++.h>
using namespace std;

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

int n, g[5003], v[5003], G;
int dp[2][10003];

int main()
{
    int i, j, profitMax = 0, L0, L1;
    in >> n >> G;
    for (i = 1; i <= n; i++)
        in >> g[i] >> v[i];
    L0 = 0; L1 = 1;
    dp[L0][g[1]] = v[1];
    for (i = 2; i <= n; i++)
    {
        for (j = 1; j <= G; j++)
            if(g[i] <= j) dp[L1][j] = max(dp[L0][j], dp[L0][j-g[i]]+v[i]);
            else dp[L1][j] = dp[L0][j];
        swap(L0, L1);
    }
    for(j = 1; j <= G; j++)
        profitMax = max(profitMax,dp[L0][j]);
    out << profitMax << "\n";
    return 0;
}