#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(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]);
   }

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

   printf("%d", sol);


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