#include <bits/stdc++.h>

using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

const int kN = 1e4 + 5;

int dp[2][kN];
int g[kN], v[kN];
int n, G;

int main(){
   ios_base::sync_with_stdio(false);

   fin >> n >> G;
   for (int i = 1; i <= n; i++){
      fin >> g[i] >> v[i];
   }
   for (int i = 1; i <= n; i++){
      for (int j = 0; j <= G; j++){
         dp[i % 2][j] = dp[1 - i % 2][j];
         if (j - g[i] >= 0){
            dp[i % 2][j] = max(dp[i % 2][j], dp[1 - i % 2][j - g[i]] + v[i]);
         }
      }
   }
   fout << dp[n % 2][G];
}