#include <bits/stdc++.h>

using namespace std;

const int GMAX=7e5+2;

bitset <GMAX> A;

struct obiect
{
    int G, P;
};

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=s; j>=0; j--)
            if(A[j])
                sol[j+W]=max(sol[j+W], (sol[j]+P));

        A|=(A<<W);

        s+=W;
    }

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

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

    return 0;
}