#include <stdio.h>
#include <vector>

using namespace std;

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

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

vector<int> dp_1(GMAX, 0);
vector<int> dp_2(GMAX, 0);

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) {
      for (int j = 0; j <= G; ++j) {
         if (j < c[i]) {
            dp_2[j] = dp_1[j];
         } else {
            dp_2[j] = max(dp_1[j - c[i]] + v[i], dp_1[j]);
         }
      }
      dp_2.swap(dp_1);
   }

   printf("%d", dp_1[G]);


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