#include <cstdio>
#include <vector>
#include <limits>
using namespace std;

vector<int> weight, profit, DP;
int N, G;

int main()
{
  freopen("rucsac.in", "r", stdin);
  freopen("rucsac.out", "w", stdout);

  scanf("%d%d", &N, &G);
  weight.resize(N);
  profit.resize(N);
  DP.resize(G + 1, numeric_limits<int>::min() / 3);
  DP[0] = 0;

  for (int i = 0; i < N; ++i)
    scanf("%d%d", &weight[i], &profit[i]);
  
  
  int rightMost = 0;
  for (int i = 0; i < N; ++i)
    for (int j = rightMost; j >= 0; --j)
      if (j + weight[i] <= G) {
	DP[j + weight[i]] = max(DP[j + weight[i]], DP[j] + profit[i]);
	rightMost = max(rightMost, j + weight[i]);
      }

  printf("%d\n", DP[G]);
  
  return 0;
}