unittest
{
	assert( [ "3 8", "3 30", "4 50", "5 60" ].parse.expand.solve == 90 );
	assert( [ "5 5", "1 1000000000", "1 1000000000", "1 1000000000", "1 1000000000", "1 1000000000" ].parse.expand.solve == 5000000000 );
	assert( [ "6 15", "6 5", "5 6", "6 4", "6 6", "3 5", "7 2" ].parse.expand.solve == 17 );
}



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 nw = input.front.split.to!( long[] );
	auto wvs = new long[][]( nw[ 0 ], 2 );
	foreach( ref wv; wvs )
	{
		input.popFront;
		wv = input.front.split.to!( long[] );
	}
	return tuple( nw[ 1 ], wvs );
}

auto solve( long t, long[][] wvs )
{
	auto dp = new long[][]( wvs.length + 1, t + 1 );
	
	for( auto i = 1L; i < dp.length; i++ )
	{
		auto w = wvs[ i - 1 ][ 0 ];
		auto v = wvs[ i - 1 ][ 1 ];
		
		for( auto g = 1L; g < dp[ i ].length; g++ )
		{
			if( 0 <= g - w )
			{
				dp[ i ][ g ] = max(					// 価値の総和が大きくなるほうを選ぶ
					dp[ i - 1 ][ g ],				// 品物を入れない場合
					dp[ i - 1 ][ g - w ] + v		// 品物を入れる場合
				);
			}
			else
			{
				dp[ i ][ g ] = dp[ i - 1 ][ g ];
			}
		}
	}
	
	return dp[ $ - 1 ][ $ - 1 ];
}
