#include <iostream>
#include <fstream>
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
typedef long long ll;
ll dp[2][10001], w[5001], v[5001];
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n, k, i, G, j, g;
  fin >> n >> G;
  dp[0][0] = 0;
  for (i = 1; i <= G; i++){
    dp[0][i] = -(ll)1e15;
  }
  for (i = 1; i <= n; i++){
    fin >> w[i] >> v[i];
  }
  for (i = 1; i <= n; i++){
    for (g = 0; g <= G; g++){
      if (g < w[i])
        dp[1][g] = dp[0][g];
      else
        dp[1][g] = max(dp[0][g], v[i] + dp[0][g - w[i]]);
    }
    for (g = 0; g <= G; g++){
      dp[0][g] = dp[1][g];
      dp[1][g] = -(ll)1e15;
    }
  }
  ll rez = 0;
  for (g = 0; g <= G; g++) rez = max(rez, dp[0][g]);
  fout << rez;
  return 0;
}