#include <fstream>
#include <algorithm>
using namespace std;
int const NM = 1e4 + 7;
int dp [NM];
char const in [] = "rucsac.in";
char const out [] = "rucsac.out";
ifstream cin (in);
ofstream cout (out);
int main()
{
    int n , i , g , a , b , from = 0 , j;
    cin >> n >> g;
    for(i = 1 ; i <= n ; ++ i)
    {
        cin >> a >> b;
        for(j = from ; j > 0 ; -- j)
            if (dp [j])
                dp [a + j] = max (dp [a + j] , dp [j] + b);
        dp [a] = max (b , dp [a]);
        from = min (from + a , g);
    }
    cout << *max_element (dp + 1 , dp + g + 1);
    return 0;
}