/********************************************************************
*   This program is written to solve instances of the { 0,1 } knapsack
* problem.  
*
*  This program reads input from an external file, supplied to the
* program upon invocation (e.g.  ./knapsack <input.txt).
*  
*  The format of the input file is 
*     numItems  maxWeight
*       benefit_1  weight_1  benefit_2  weight_2 ... benefit_n weight_n
*     numItems maxWeight
*       benefit_1  weight_1  benefit_2  weight_2 ... benefit_k weight_k
*     ...
*     ...
*     0 0
* 
* In other words, the number of items in the instance, followed by the
* maximum allowed weight.  The next line contains all of the i
* benefit, weigh pairs (but there's no commas in between them!!).   
*
*   The input is terminated by two 0s.  
*******************************************************************/

import java.io.*;
import java.util.*;

class Knapsack
{
   public static void main (String args[]) // entry point from OS
   {
      new MyClass(new Scanner(System.in));  // create dynamic entry point
   }
}

class MyClass {

   MyClass (Scanner s)
   {
      Scanner ls;
      int numItems, maxWeight, k;
      int benefit[], weight[];

    //***  Read in the initial nuumItems, maxWeight pair
      ls = new Scanner(s.nextLine());
      numItems = ls.nextInt();
      maxWeight = ls.nextInt();
 
    while ( (numItems != 0) && (maxWeight != 0) )
    {
      // *** Read in all the data for the items
          benefit = new int [numItems+1];
          weight = new int [numItems+1];
          ls = new Scanner(s.nextLine());
          for (k = 1; k <= numItems; k++)
              {  
                  benefit [k] = ls.nextInt();
                  weight [k] = ls.nextInt();
              }


      /************************************************
        Here is where you want to insert your
      code to solve this problem.    

     Note that you need to define some more appropriate
     variables for your code.  
     **************************************************/


      // ***  Read in the next numItems, maxWeight pair
      ls = new Scanner(s.nextLine());
      numItems = ls.nextInt();
      maxWeight = ls.nextInt();
   }  
 
 }

}  //**  end of the "MyClass" class