#include <fstream>
#include <algorithm>
using namespace std;
struct knap {
    int w , p;
}v [5001];
int dp [10001];
ifstream f ("rucsac.in");
ofstream g ("rucsac.out");
int main()
{
    int n , G , gmax = 0;
    f >> n >> G;
    for (int i = 1 ; i <= n ; ++ i){
        f >> v [i] . w >> v [i] . p;
        for(int j = gmax ; j >= 0 ; -- j)
            if (dp [j] || ! j){
                dp [j + v [i] . w] = max (dp [j] + v [i] . p , dp [j + v [i] . w]);
                gmax = max (gmax , j + v [i] . w);
            }
    }
    g << *max_element (dp + 1 , dp + 1 + G);
    return 0;
}