#!/usr/bin/ruby

# Facebook User Bin Crash Puzzle
# 12/26/2009
# tom.luo@gmail.com


# ----------------------------------------------------
# The item struct 
class Item
  attr_accessor :weight, :cost, :ratio
  def initialize(weight,cost)
      @weight=weight
      @cost = cost
      @ratio = cost.to_f/weight.to_f
  end
end
# ----------------------------------------------------

# ----------------------------------------------------
# The Greatest common divisor
# gcd is not a build-in function until Ruby 1.9 
def f_gcd(a, b)
  while a != b
    if a > b
      a = a-b
    else
      b = b-a
    end
  end
  return a
end
# ----------------------------------------------------


# ----------------------------------------------------
# the core function that calculates the min cost for 
# the target weight.
# Merry Christmas

def Christmas(target,items)
# create and populat an array that holds the minimum cost of each weight

costs =[]

(0..target-1).each do |i|
     least =nil
      items.each do |item|
          w = item.weight
          c = item.cost
          # -------------------------
          if i >= w
             c += costs[i-w]
          end
          # ------------------------
         least = c if least.nil? || least>c 
       end
       costs[i] =  least
        # puts "costs[#{i}] = #{costs[i]}"  
     end 
 return costs[target-1]
end

# ----------------------------------------------------

# =====================================================


# ----------------------------------------------------
# Main
file_name=ARGV[0]

file=File.open(file_name,"r")
inventory_list = file.readlines

# ----------------------------------------------------
# get the min number of pounds of weight that must be ejected
target = inventory_list.delete_at(0).to_i
# ----------------------------------------------------


# ----------------------------------------------------
# collect the SKU list into an array of the Item struct
# ----------------------------------------------------
items = []
inventory_list.each do |line|
 sku, weight, cost=line.split()
 cost = cost.to_i
 weight = weight.to_i
 items << Item.new(weight,cost)
end
# -----------------------------------------

# ----------------------------------------------------
# delete those items that weight less but cost more
items.each do |x|
items.delete_if {|y| y.weight < x.weight && y.weight * y.cost > x.weight * x.cost }
end
# items.sort_by {|x| x.weight}.reverse
# ----------------------------------------------------


# ----------------------------------------------------
# devide both target and each weight by the GCD 
# therefore reduce the number of loops potentioally
# optimize the target and the inventory list
# ----------------------------------------------------
gcd = f_gcd(target,items[0].weight)
items.each { |item| gcd = f_gcd(gcd, item.weight)}
target = target/gcd
items.each { |i| i.weight =i.weight/gcd }
# ----------------------------------------------------

puts "#{Christmas(target,items)}\n"
# End of Main
# ----------------------------------------------------