#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. Putem fixa intai i si apoi j sau
intai j si apoi i, atat timp cat i si j sunt parcurse de la 1 la n, respectiv
de la 1 la g, datorita formei recurentei.
Daca intai fixam i, vom avea calculate liniile 1,2,...,i-1, iar formula
implica doar linia i-1.
Daca intai fixam j, vom avea calculate coloanele 1,2,...,j-1, iar formula
contine coloana j-p[i] <=j-1 pentru p[i] >=1. Daca p[i] = 0 sau maximul din
formula este dp[i-1][j], atunci in continuare e corect: de la coloana j avem
deja calculate liniile mai mici decat linia curenta, deci si linia i-1.
Pentru eficienta memoriei, observam ca ne folosim doar de liniile i si i-1
intotdeauna si putem reduce nr. de linii ale matricei dp la 2. In ceea ce
priveste coloanele, e posibil sa avem nevoie de mai mult decat ultimele 2.
Totusi, daca folosim memoria eficient, este obligatoriu ca intai sa fixam
linia i si apoi sa fixam coloana j, nu invers. Altfel nu vom obtine rezultatul
corect.

*/

int main() {
  int n, g, x;
  vector<int> w, p;
  fin >> n >> g;
  vector<vector<int>> dp(2, vector<int>(g + 1, 0));
  // dp[0][i] = 0, dp[i][0] = 0, i=0,...,n si i = 0,...,g.
  // Punem o valoare oarecare, in cazul acesta -1, pe prima pozitie
  // in w si p, pentru a putea incepe indexarea efectiva de la 1.
  w.push_back(-1);
  p.push_back(-1);

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

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

  fout << dp[0][g];  // sau dp[1][g]
  return 0;
}