#include <bits/stdc++.h>
using namespace std;

const int Nmax = 5005;
const int Gmax = 10005;

int W[Nmax]; /// Greutatea
int P[Nmax]; /// Pretul
int G, N;
int dp[3][Gmax]; /// pretul maxim care se poate obtine alegand unele din primele i elemente (rezumata la 2 linii) obiecte obtinand greutatea j

void Read()
{
    ifstream fin("rucsac.in");
    fin >> N >> G;
    for (int i = 1; i <= N; i++)
        fin >> W[i] >> P[i];
    fin.close();
}

void DP()
{
    int i, lin, j;
    /// Initializare
    lin = 0;
    /// d[0][j] = 0, j = 1..G -> castigul maxim poate fi doar prin alegerea primului obiect, sau nu
    dp[0][W[1]] = P[1]; /// alegem primul obiect -> putem obrine pretul P[1] cu greutatea W[1]

    for (i = 2; i <= N; i++)
    {
        lin = 1 - lin;

        for (j = 0 ; j <= G; j++)
            if (W[i] <= j)
                dp[lin][j] = max(dp[1 - lin][j],                   /// Nu adaug obiectul i asa ca pastrez suma maxima precedenta pentru greutatea j
                                 dp[1 - lin][j - W[i]] + P[i]);    /// sau adaug ob i la greutatea complementara si adaug costul
            else
                dp[lin][j] = dp[1 - lin][j]; /// depasesc G si iau din oficiu suma max precedenta fara ob i
    }

    /**
    */
    int M = dp[lin][1];
    for (j = 2; j <= G; j++)
        M = max(M, dp[lin][j]); /// maximul obtinut cu obiecte de o greutate totala <= G

    ofstream fout("rucsac.out");
    fout << M << "\n";
    fout.close();
}

int main()
{
    Read();
    DP();
    return 0;
}