#include <cstdio>
#include <algorithm>
using namespace std;

const int maxN = 5000;
int weight[maxN + 5], profit[maxN + 5];
int dp[maxN + 5];

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

  int N, G, ans = 0;
  scanf("%d %d", &N, &G);
  for(int i = 1; i <= N; ++ i)
    scanf("%d %d", &weight[i], &profit[i]);

  for(int i = 1; i <= N; ++ i) {
    for(int j = G - weight[i]; j >= 0; -- j) {
      int k = j + weight[i];
      dp[k] = max(dp[k], dp[j] + profit[i]);
      ans = max(ans, dp[k]);
    }
  }

  printf("%d\n", ans);
  return 0;
}