#include <bits/stdc++.h>

using namespace std;

const int NMAX = 5555;

int dp[2][10005], w[NMAX], p[NMAX];
int N, G; 

int main() {
  freopen("rucsac.in", "r", stdin);
  freopen("rucsac.out", "w", stdout);
  scanf("%d %d", &N, &G);
  for (int i = 1; i <= N; i++) {
    scanf("%d %d", w + i, p + i);
  }
  for (int i = 0; i <= G; i++) dp[0][i] = 0;
  int l = 0;
  for (int i = 1; i <= N; i++, l = 1 - l) {
    for (int j = 0; j <= G; j++) {
      dp[1 - l][j] = dp[l][j];
      if (j >= w[i]) {
        dp[1 - l][j] = max(dp[1 - l][j], dp[l][j - w[i]] + p[i]);
      }
    }
  }
  printf("%d\n", dp[1][G]);
}