#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int DIM = 5007;
const int DIM1 = 1e4+7;
int W[DIM];
int P[DIM];

int dp[2][DIM1];

int main()
{
    ios::sync_with_stdio(false);
    in.tie(0);
    int N,G;
    in >> N >> G;
    for(int i = 1;i <= N;i++)
        in >> W[i] >> P[i];

        int l = 0;
    for(int i = 1; i <= N; i++, l = 1 - l)
        for(int cw = 0;cw <= G;cw++)
        {
          dp[1-l][cw]=dp[l][cw];
          if(W[i] <= cw)
            dp[1-l][cw] = max(dp[1-l][cw],dp[l][cw - W[i]] + P[i]);
        }
        out << dp[l][G];
    return 0;
}