#include    <iostream>
#include    <stdio.h>
#include    <cstring>

using namespace std;

const int nMax = 5005;
const int gMax = 10005;

struct obiect
{
    int greutate, valoare;
}o[nMax];

int n,g;

int rucsacDinamic(int W, int numObj)
{
    int rucsac[W+1];
    memset(rucsac, 0, sizeof rucsac);

    for(int i=1; i<=numObj; ++i)
        for(int j=W; j>=0; --j)
            if(o[i].greutate <= j)
                rucsac[j] = max(rucsac[j], rucsac[j - o[i].greutate] + o[i].valoare);

    return rucsac[W];
}

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

    scanf("%d %d", &n, &g);

    for(int i=1; i<=n; ++i)
    {
        scanf("%d %d", &o[i].greutate, &o[i].valoare);
    }

    printf("%d", rucsacDinamic(g,n));

    return 0;
}