#include <fstream>

using namespace std ;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n, pack, weight[5002], value[5002], dp[10002] ;

int main()
{

    cin >> n >> pack ;

    for (int i = 1 ; i <= n ; i ++)
        cin >> weight[i] >> value[i] ;

    for (int i = 1 ; i <= n ; i ++)
    {

        for (int j = pack ; j >= weight[i] ; j --)
            dp[j] = max (dp[j], dp[j - weight[i]] + value[i]) ;

    }

    cout << dp[pack] ;

    return 0 ;

}