#include <bits/stdc++.h>
using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int greutate[5005],profit[5005];
int rucsac[3][10005];

int main()
{
    int nr_obiecte,capacitate_max,i,j,linie_folosita;

    f>>nr_obiecte>>capacitate_max;

    for (i=1;i<=nr_obiecte;i++)
        f>>greutate[i]>>profit[i];

    for (i=1;i<=nr_obiecte;i++) /// i = obiectul curent
    {
        linie_folosita = i%2;

        for (j=1;j<=capacitate_max;j++) /// j = greutate curenta
        {
            rucsac[linie_folosita][j] = rucsac[1-linie_folosita][j];
            if (greutate[i]<=j)
                rucsac[linie_folosita][j] = max(rucsac[1-linie_folosita][j],rucsac[1-linie_folosita][j-greutate[i]]+profit[i]);
        }
    }

    if (nr_obiecte%2==0)
        g<<rucsac[0][capacitate_max];
    else
        g<<rucsac[1][capacitate_max];

    return 0;
}