#include <cstdio>

#define max(a, b) ((a) > (b) ? (a) : (b))

using namespace std;

int dp[2][10005];

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    int n, G, W, P;
    scanf("%d %d", &n, &G);

    /// tablou bidimensional dp, astfel incat dp[i][g] sa memoreze castigul maxim care se poate obtine alegand obiecte dintre primele k, astfel incat greutatea totala a lor sa nu depaseasca g
    int l = 0;
    for(int i = 1; i <= n; ++i, l = 1 - l)
    {
        scanf("%d %d", &W, &P);
        for(int g = 0; g <= G; ++g)
        {
            /// daca greutatea obiectului i depaseste greutatea curenta g atunci el nu poate fi luat. atunci castigul maxim obtinut din primele i obiecte = castigul maxim obtinut din primele i-1 obiecte
            dp[1-l][g] = dp[l][g];

            /// daca greutatea maxima curenta g atunci putem lua obiectul k
            if(W <= g)
                dp[1-l][g] = max(dp[1-l][g], dp[l][g-W] + P);
        }
    }

    /*for(int i = 1; i <= n; ++i)
    {
        for(int g = 0; g <= G; ++g) cout << dp[i][g] << " ";
        cout << '\n';
    }*/
    printf("%d", dp[l][G]);
    return 0;
}