#include <bits/stdc++.h>

using namespace std;

const int NMAX = 5555;

int dp[5005][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;
  for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= G; j++) {
      dp[i][j] = dp[i - 1][j];
      if (j >= w[i]) {
        dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + p[i]);
      }
    }
  }
  printf("%d\n", dp[N][G]);
}