#include <bits/stdc++.h>

using namespace std;

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

const int SIZE = 5005;
const int G_SIZE = 10005;

int N, G, w[SIZE], p[SIZE];

int dp[G_SIZE], sol;

/*
    Dinamica:
        dp[i][G] = profitul maxim obtinut alegand obiecte din
        multimea primelor i obiecte a caror greutate totala este G

    Recurenta:
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + p[i]

        ( dp[i - 1][j] = profitul maxim in cazul in care NU adaugam obiectul i
          dp[i - 1][j - w[i]] + p[i] = profitul maxim obtinut alegand obiecte
          din multimea [1, i - 1], cu greutatea j - w[i] (se va adauga w[i]
          sa se obtina greutatea j) la care se adauga profitul obiectului i

    Sol: dp[n][G]


    Observatie:
        1) pentru a genera linia i se foloseste numai linia i - 1, deci putem folosi
           o matrice cu 2 linii
        2) daca parcurgem sirul greutatiilor in sens descrescator, putem folosi
           o singura linie, adica un vector


*/

int main()
{
    fin >> N >> G;

    for(int i = 1; i <= N; ++i)
        fin >> w[i] >> p[i];

    dp[0] = 0;
    sol = 0;

    for(int i = 1; i <= N; ++i)
        for(int j = G - w[i]; j >= 0; --j)
        {
            //daca obiectul ne da o greutate identica cu profit mai bun
            dp[j + w[i]] = max(dp[j + w[i]], dp[j] + p[i]);
            sol = max(sol, dp[j + w[i]]);
        }

    fout << sol;

    return 0;
}