#include <bits/stdc++.h>

using namespace std;

const int GMAX=5e7+2;

bitset <GMAX> A;

int N, G, i, W, P, j;

int sol[GMAX], ans, s;

int main()
{
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);

    scanf("%d%d", &N, &G);

    A[0]=1;

    for(i=1; i<=N; i++)
    {
        scanf("%d%d", &W, &P);

        for(j=min(G-W, s); j>=0; j--)
            if(A[j])
            {
                A.set(j+W);

                sol[j+W]=max(sol[j+W], (sol[j]+P));
            }

        s+=W;
    }

    for(i=G; i>=0; i--)
        ans=max(ans, sol[i]);

    printf("%d\n", ans);

    return 0;
}