unittest
{
	assert( [ "3 8", "3 30", "4 50", "5 60" ].parse.expand.solve == 90 );
	assert( [ "1 1000000000", "1000000000 10" ].parse.expand.solve == 10 );
	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 vm = reduce!( ( a, wv ) => a + wv[ 1 ] )( 0L, wvs ) + 1;
	auto wm = t + 1;
	
	// dp[ wvi ][ vi ]＝「価値がvi以上になる最小の重量」を計算（条件を満たせない場合はwmを入れる）
	auto dp = new long[][]( 1 + wvs.length, 1 + vm );
	
	dp[ 0 ][ 1 .. $ ] = wm;		// 何も入れない場合は価値を1以上にできない
	for( auto wvi = 1L; wvi < dp.length; wvi++ )
	{
		auto w = wvs[ wvi - 1 ][ 0 ];
		auto v = wvs[ wvi - 1 ][ 1 ];
		for( auto vi = 1L; vi < dp[ wvi ].length; vi++ )
		{
			// wvs[ wvi ]の品物を入れない場合（wvs[ 0 .. wvi - 1 ]の選択結果そのまま）
			auto dp_p1 = dp[ wvi - 1 ][ vi ];
			
			// wvs[ wvi ]の品物を入れる場合（wvs[ 0 .. wvi - 1 ]の選択結果 ＋ wvs[ wvi - 1 ]の重量）
			auto dp_p2_vi = vi - v;
			auto dp_p2    = ( 0 <= dp_p2_vi ) ? dp[ wvi - 1 ][ dp_p2_vi ] + w : w;
			
			// 軽いほうを取る
			dp[ wvi ][ vi ] = min( dp_p1, dp_p2 );
		}
	}
	
	// 重量が上限未満での最大価値が答え
	return dp[ $ - 1 ].assumeSorted.countUntil( wm ) - 1;
}
