#include <bits/stdc++.h>
using namespace std;
int const NM = 10007;
int dp [NM];
#define cin fin
#define cout fout
ifstream fin ("rucsac.in");
ofstream fout ("rucsac.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;
}