#include <bits/stdc++.h>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int NMAX=5005,GMAX=10005;
int n,G,l,w[NMAX],p[NMAX],dp[2][GMAX];
int main()
{
    f>>n>>G;
    for(int i=1; i<=n; i++)
        f>>w[i]>>p[i];
    ///dp[i][curent_weight]- profitul maxim pe care-l putem obtine adaugand o submultime a primelor i obiecte,insumand greutatea current_weight
    ///linia l-solutia pentru elementul (i-1)
    ///linia 1-l-linia pe care construim solutia
    for(int i=1; i<=n; i++,l=1-l)
        for(int current_weight=0; current_weight<=G; current_weight++)
        {
            ///copiem de pe cealalta linie
            dp[1-l][current_weight]=dp[l][current_weight];
            ///incercam sa adaugam obiectul i la solutia anterioara
            if(w[i]<=current_weight)
                dp[1-l][current_weight]=max(dp[1-l][current_weight],dp[l][current_weight-w[i]]+p[i]);
        }
    ///solutia se afla in dp[n][G],adica pe linia l
    g<<dp[l][G];
    return 0;
}