#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

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

/*
Observatie de citit dupa rezolvarea efectiva:
// dp[i][j] in functie de dp[i][j-1] nu se poate.
// dp[i][j] = dp[i][j-1], daca solutia maxima cu ghiozdanul de capacitate j
// are greutate <= j-1. Altfel, nu putem determina dp[i][j] in functie
// de dp[i][j-1].
// Totusi, am putea determina dp[i][j+1] = max(dp[i-1][j+1], p[i] +
dp[i-1][j+1-w[i]]),
// dar aceasta e aceeasi recurenta cu cea de mai jos.


dp[i][j] = profitul maxim care poate fi obtinut folosind doar obiecte
dintre primele i si un ghiozdan cu capacitate maxima j.
Vrem sa gasim dp[i][j] in functie de dp[i-1][j].
Obiectul i poate sa fie sau sa nu fie folosit in solutia cu profit maxim.
Solutia optima pentru cazul in care obiectul i nu e folosit
este dp[i][j] = dp[i-1][j].
Solutia optima pentru cazul cand obiectul i e folosit este
dp[i][j] = p[i] + dp[i-1][j-p[i]].
Solutia optima in general este maximul dintre solutia optima pentru cazul cu
obiectul i nefolosit si solutia optima pentru cazul cu obiectul i folosit.
dp[i][j] = max(dp[i-1][j], p[i] + dp[i-1][j-p[i]]), oricare ar fi i=1,...,n
si j=1,...,g.
Relatia de mai sus e suficienta pentru a construi matricea: avem prima linie
si prima coloana initializate cu 0, iar pe i si pe j le parcurgem crescator.
Prima linie si prima coloana au indicii 0. Intai fixam j, apoi i.
*/

int main() {
  int n, g, x;
  vector<int> w, p;
  fin >> n >> g;
  vector<vector<int>> dp(n + 1, vector<int>(g + 1, 0));
  // dp[0][i] = 0, dp[i][0] = 0, i=0,...,n si i = 0,...,g.

  for (int i = 0; i < n; i++) {
    fin >> x;
    w.push_back(x);
    fin >> x;
    p.push_back(x);
  }

  for (int j = 1; j <= g; j++)
    for (int i = 1; i <= n; i++)
      if (j >= w[i])  // Trebuie verificat daca ob. i poate fi pus in rucsacul
                      // de cap. j
        dp[i][j] = max(dp[i - 1][j], p[i] + dp[i - 1][j - w[i]]);
      else
        dp[i][j] = dp[i - 1][j];

  fout << dp[n][g];
  return 0;
}