import java.io.File;
import java.util.Scanner;
import java.util.Arrays;

class knapsack
{
  static class Item
  {
    int weight;
    int value;

    /*
     * Item constructor
     *   inputs: the weight w and value v
     *   output: a new Item!
     */
    public Item( int w, int v )
    {
      this.weight = w;
      this.value = v;
    }

    public String toString()
    {
      return "(wt: " + this.weight + ", value: " + this.value + ")";
    }
  }

  // globals for mesuring performance
  public static final boolean COUNT_CALLS = true;
  public static final boolean PRINT_FINAL_TABLE = false;
  public static final boolean PRINT_CALLS = false;

  /* Human time is important, too!
   */
  public static void pl(String s) {System.out.println(s);}
  public static void p(String s) {System.out.print(s);}

  /*
   * main function for the knapsack class
   *   all of the user interaction happens here
   */
  public static void main(String[] args)
  {
    if (args.length < 1) { // filename will be args[0]
      pl("Run:   java change <filename>");
      System.exit(0);
    }

    String filename = args[0]; // nicer variable name
    Scanner fileScanner = null;

    try {  // need a try/catch in case the file isn't present
      fileScanner = new Scanner( new File( filename ) );
    } catch (Exception e) {
      pl("Caught the error " + e);
      System.exit(0);
    }

    // parse the file
    int number_of_items = fileScanner.nextInt();
    pl("There are " + number_of_items + " items.");

    Item[] items = new Item[number_of_items];
    for (int i=0 ; i<number_of_items; ++i) 
    { 
      int w = fileScanner.nextInt();
      int v = fileScanner.nextInt();
      items[i] = new Item( w, v );
    }
    pl( "Items are " + Arrays.toString( items ) );

    // for user input
    Scanner inputScanner = new Scanner( System.in );

    while (true) {
        // reset count of calls...
        total_calls = 0;

        pl("\nOptions:");
        pl("  (1) Run raw recursive algorithm");
        pl("  (2) Run memoized (recursion without repeat calls)");
        pl("  (3) Run dynamic programming (a bottom-up table)");
        pl(" (42) Quit");
        p("Choose wisely: ");
        int user_choice = inputScanner.nextInt();

        if (user_choice == 42) break;
        if (user_choice < 1 || user_choice > 3) continue;

        // get knapsack value
        int knapsack_capacity = -1;
        do {
          p("How much can you carry? ");
          knapsack_capacity = inputScanner.nextInt();
        } while (knapsack_capacity < 0);

        // timing code
        long current_time = System.currentTimeMillis();

        // reset the tables
        reset_tables( knapsack_capacity );

        // main call
        int maximum_carry_value = 0;
        if (user_choice ==  1) {
          maximum_carry_value = max_value_recursion( knapsack_capacity, items );
        } else if (user_choice == 2) {
          maximum_carry_value = max_value_memoized( knapsack_capacity, items );
        } else if (user_choice == 3) {
          maximum_carry_value = max_value_dp( knapsack_capacity, items );
        } 

        // end of timing
        long final_time = System.currentTimeMillis();
        double total_time = (final_time - current_time)/1000.0;

        // report results
        pl("The maximum \"carriable\" value is ** " + maximum_carry_value + " **");

        // print items to take - go through the other table...
        p("The items to carry are\n");
        //int coin_freq = new int[values.length];
        while (true && knapsack_capacity>0) {
          Item next_item = items_carried_table[knapsack_capacity];
          pl( "  " + next_item );
          knapsack_capacity -= next_item.weight;
        }
        pl("");

        // report timing
        pl("Total time taken: " + total_time + " seconds.");
        if (COUNT_CALLS)
          pl("  Number of calls: " + total_calls );
    }

    pl( "\n\nOur motto:\n\n  We run faster by doing LESS!\n\n" );

  }

  public static final int UNKNOWN = -1;
  public static final int INF = 1000000000;
  public static int total_calls = 0;
  public static int[] max_carryable_value_table = null;
  public static Item[] items_carried_table = null;

  public static void reset_tables( int knapsack_capacity )
  {
    // create table of results
    max_carryable_value_table = null;
    items_carried_table = null;

    max_carryable_value_table = new int[ knapsack_capacity+1 ]; 
    items_carried_table = new Item[ knapsack_capacity+1 ];

    for (int i=0 ; i<knapsack_capacity+1 ; ++i) {
      max_carryable_value_table[i] = 0;  
      items_carried_table[i] = null;
    }
    // base cases
    max_carryable_value_table[0] = 0;
    items_carried_table[0] = null;
  }


  /*
   * max_value_memoized
   *  inputs: the capacity and the list of available items
   *  output: the maximum obtainable value
   *  approach: this function caches a table of results
   *            as it goes, so that each distinct call needs
   *            to happen at most once, aka "memoization"
   */
  public static int max_value_memoized( int capacity, Item[] items )
  {
    if (PRINT_CALLS)
      pl( "START of call with capacity " + capacity );
    if (COUNT_CALLS)
      ++total_calls;

    if (capacity < 0) return -INF; // impossible!
    if (capacity == 0) return 0;
    if (max_carryable_value_table[capacity] > 0) 
      return max_carryable_value_table[capacity];

    int max_value = max_value_memoized( capacity-1, items ); // lose it!
    Item item_yielding_max_value = null; // lost!

    // try all of the "use it" possibilities
    for (int i=0 ; i<items.length ; ++i)
    {
      int smaller_capacity = capacity-items[i].weight;
      int new_value = max_value_memoized( smaller_capacity, items ) + items[i].value; 

      if (new_value > max_value)
      {
        max_value = new_value;
        item_yielding_max_value = items[i];
      }
    }

    max_carryable_value_table[capacity] = max_value;
    items_carried_table[capacity] = item_yielding_max_value;

    if (PRINT_CALLS)
      pl("END of call with capacity: " + capacity);

    return max_value;
  }

  /*
   * max_value_dp
   *  inputs: the capacity and the list of available items
   *  output: the maximum obtainable value
   *  approach: this function builds a table of partial results
   *            that gets used to compute the best possible value
   *            aka "dynamic programming"
   */
  public static int max_value_dp( int capacity, Item[] items )
  {
    if (PRINT_CALLS)
      pl( "START of call with capacity " + capacity );
    if (COUNT_CALLS)
      ++total_calls;

    for (int next_capacity = 1; next_capacity<=capacity ; ++next_capacity)
    {
      int max_value = max_carryable_value_table[ next_capacity-1 ]; // lose it
      Item item_yielding_max_value = null; // lost item!

      for (int i = 0 ; i < items.length ; ++i)
      {
        int smaller_capacity = next_capacity - items[i].weight;
        if (smaller_capacity < 0) continue; // can't use it!

        int new_value = max_carryable_value_table[ smaller_capacity ] + items[i].value;
        if (new_value > max_value)
        {
          max_value = new_value;
          item_yielding_max_value = items[i];
        }
      }
      // store other results as needed...
      items_carried_table[next_capacity] = item_yielding_max_value;
      max_carryable_value_table[next_capacity] = max_value;
    }

    if (PRINT_CALLS)
      pl("END of call with capacity: " + capacity);

    return max_carryable_value_table[ capacity ]; // done!
  }

  /*
   * max_value_recursion
   *  inputs: the capacity and the list of available items
   *  output: the maximum obtainable value
   *  approach: this function uses raw recursion - no tables 
   */
  public static int max_value_recursion( int capacity, Item[] items )
  {
    if (PRINT_CALLS)
      pl( "START of call with capacity " + capacity );
    if (COUNT_CALLS)
      ++total_calls;

    if (capacity < 0) return -INF; // impossible!
    if (capacity == 0) return 0;

    int max_value = max_value_recursion( capacity-1, items );
    Item item_yielding_max_value = null; // no item!

    for (int i = 0 ; i < items.length ; ++i)
    {
      int smaller_capacity = capacity - items[i].weight;
      if (smaller_capacity < 0) continue; // can't use it
      int new_value = max_value_recursion( smaller_capacity, items ) + items[i].value;
      if (new_value > max_value)
      {
        max_value = new_value;
        item_yielding_max_value = items[i];
      }
    }

    // note that these are for reporting results at the end -
    // they don't get used to speed the computation so that
    // this method represents a purely recursion-based computation
    max_carryable_value_table[capacity] = max_value;
    items_carried_table[capacity] = item_yielding_max_value;

    if (PRINT_CALLS)
      pl("END of call with capacity: " + capacity);

    return max_value;
  }
    
}