#include <stdio.h>

inline int max(int a, int b) {
   return a < b ? b : a;
}

const int NMAX =  5005;
const int GMAX = 10005;

int dp[NMAX][GMAX];

int N, G;

int v[NMAX];
int c[NMAX];

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", &c[i], &v[i]);
   }

   for (int i = 1; i <= N; ++i) {
      dp[i][0] = 0;
   }

   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) {
         if (j < c[i]) {
            dp[i][j] = dp[i - 1][j];
         } else {
            dp[i][j] = max(dp[i-1][j - c[i]] + v[i], dp[i-1][j]);
         }
      }
   }

   printf("%d", dp[N][G]);


   fclose(stdin);
   fclose(stdout);
   return 0;
}