#include <cstdio>
#include <cstring>

#define MAX 10001

using namespace std;

int superior[MAX], inferior[MAX];

int n, g;

struct object
{
    int greutate;
    int valoare;
}obiect[5001];

int maxim(int a, int b)
{
    if(a > b)
        return a;
    return b;
}

void citire()
{
    freopen("rucsac.in", "r", stdin);
    scanf("%d %d\n", &n, &g);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d\n", &obiect[i].greutate, &obiect[i].valoare);
    }
    fclose(stdin);
}

void rezolvare()
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= g; j++)
        {
            if(j >= obiect[i].greutate)
            {
                inferior[j] = maxim(superior[j], superior[j - obiect[i].greutate] + obiect[i].valoare);
            }
            else
            {
                inferior[j] = superior[j];
            }
        }
        memcpy(superior, inferior, (g+1)*sizeof(int));
    }
}

void afisare()
{
    freopen("rucsac.out", "w", stdout);
    printf("%d", inferior[g]);
    fclose(stdout);
}

int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}