#include <iostream>
#include <fstream>

using namespace std;
const int MAX_CENTRALA = 5e3;
const int MAX_X = 1e4;
const int MAX_COST = MAX_CENTRALA + MAX_X;
const int MAX_N = 1e3;
int dp[MAX_COST+1];

ifstream fin ( "energii.in" );
ofstream fout ( "energii.out" );

int profit[MAX_N+1], cost[MAX_N+1];
int main()
{
   int n, total, price;
   fin >> n >> total;

   for ( int i = 1; i <= n; i ++ )
      fin >> profit[i] >> cost[i];

   for ( int i = 1; i <= n; i ++ )
      for ( price = MAX_COST - cost[i]; price >= 0; price -- )
           dp[price+cost[i]] = max ( dp[price+cost[i]], dp[price] + profit[i] );

   for ( price = 0; price <= 9; price ++ )
      printf ( "%d :%d\n", price, dp[price] );

   for ( price = 0; price <= MAX_COST && dp[price] < total; price ++ );

   fout << price;
    return 0;
}