unittest
{
	assert( [ "2 60", "10 10", "100 100" ].parse.expand.solve == 110 );
	assert( [ "3 60", "10 10", "10 20", "10 30" ].parse.expand.solve == 60 );
	assert( [ "3 60", "30 10", "30 20", "30 30" ].parse.expand.solve == 50 );
	assert( [ "10 100", "15 23", "20 18", "13 17", "24 12", "18 29", "19 27", "23 21", "18 20", "27 15", "22 25" ].parse.expand.solve == 145 );
}



import std.algorithm;
import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto nt = input.front.split.to!( long[] );
	auto abs = new long[ 2 ][ nt[ 0 ] ];
	foreach( ref ab; abs )
	{
		input.popFront;
		ab = input.front.split.to!( long[] );
	}
	return tuple( nt[ 1 ], abs );
}

auto solve( long t, long[ 2 ][] abs )
{
	auto mt = 0L;
	auto md = 0L;
	foreach( ab; abs )
	{
		mt += ab[ 0 ];
		md += ab[ 1 ];
	}
	if( mt <= t ) return md;
	
	auto dp = new long[][]( 1 + abs.length, 1 + t );
	foreach( ref dpp; dp ) dpp[] = -1;
	dp[ 0 ][ 0 ] = 0;
	abs.sort();
	foreach( long i, ab; abs )
	{
		foreach( long j; 0L .. dp[ i ].length )
		{
			if( dp[ i ][ j ] < 0 ) continue;
			
			// 食べない場合
			dp[ i + 1 ][ j ] = max( dp[ i + 1 ][ j ], dp[ i ][ j ] );
			
			// 食べる場合
			if( j + 1 < dp[ i ].length )
			{
				auto k = min( dp[ i ].length.signed - 1, j + ab[ 0 ] );		// ラストオーダーに間に合えば食べる時間がオーバーしても良い
				dp[ i + 1 ][ k ] = max( dp[ i + 1 ][ k ], dp[ i ][ j ] + ab[ 1 ] );
			}
		}
	}
	return dp[ $ - 1 ][ $ - 1 ];
}
