#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int maxn = 5005;
const int maxg = 10005;

int dp[2][maxg];
int W[maxn];
int P[maxn];

int main()
{
    int n, g;
    in >> n >> g;
    for(int i = 1; i <= n; i++)
        in >> W[i] >> P[i];
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= g; j++)
        {
            dp[i & 1][j] = dp[(i & 1)^ 1][j];
            if(j - W[i] >= 0)
                dp[i & 1][j] = max(dp[i&1][j], dp[(i & 1) ^ 1][j-W[i]] + P[i]);
        }
    }

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