#include <fstream>
using namespace std;

ifstream is("energii.in");
ofstream os("energii.out");

int n, G, val[10001], g[10001];
int c[10001][10001];

int main()
{
    is >> n >> G;
    for ( int i = 1; i <= n; i++ )
        is >> val[i] >> g[i];
    for ( int i = 1; i <= n; ++i )
		for ( int j = 0; j <= 2*G; ++j )
		{
			if ( j >= val[i] & c[i][j] < c[i-1][j - val[i]] + g[i] )
			{
				c[i][j] = c[i-1][j - val[i]] + g[i];
            }
		}
    bool ok = false;
    for ( int i = 0; ; ++i )
    {
        for ( int j = 0; ;++j)
        if ( c[i][j] >= G )
        {
            os << c[i][j];
            ok = true;
            break;
        }
        if ( ok )
            break;
    }
    is.close();
    os.close();
    return 0;
}