#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[2][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 = 0; i <= 1; ++i) {
      dp[i][0] = 0;
   }

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

   int ix = 0;
   for (int i = 1; i <= N; ++i, ix = 1 - ix) {
      for (int j = 0; j <= G; ++j) {
         if (j < c[i]) {
            dp[1-ix][j] = dp[ix][j];
         } else {
            dp[1-ix][j] = max(dp[ix][j - c[i]] + v[i], dp[ix][j]);
         }
      }
   }

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


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