#include <cstdio>
#include <algorithm>

using namespace std;

struct Obiect{
    int greutate, valoare;
};

int n, greutate;
Obiect obiecte[5005];
int matDinamic[2][10000];

void citire()
{
    scanf("%d %d", &n, &greutate);

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

void umplereDinamic()
{
    for(int i = 0; i < n; i++)
    {
        matDinamic[0][i] = 0;
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 1; j <= greutate; j++)
        {
            if(obiecte[i].greutate > j)
            {
                matDinamic[1][j] = matDinamic[0][j];
            }
            else
            {
                matDinamic[1][j] = max(matDinamic[0][j], obiecte[i].valoare + matDinamic[0][j - obiecte[i].greutate]);
            }
        }

        matDinamic[0][0] = 0;

        for(int j = 1; j <= greutate; j++)
        {
            matDinamic[0][j] = matDinamic[1][j];
        }
    }
}

void afisare()
{
    printf("%d", matDinamic[1][greutate]);
}

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

    citire();
    umplereDinamic();
    afisare();


    return 0;
}