#!/bin/ruby

class Item
  include Comparable
  attr_accessor :value, :route

  def initialize v
    @value = v
    @route = []
  end

  def +(other)
    @value += other.value
    @route << other.value
    self
  end

  def <=>(other)
    @value == other.value ? 0 :
    @value >  other.value ? 1 :
    -1
  end
end

class Cache
    def initialize
        @cache = {}
    end
    def _key x, y
       x.to_s + '_' + y.to_s
    end
    def [](x, y)
        @cache[_key x, y]
    end
    def []=(x, y, r)
        r_new = Item.new r.value
        r_new.route = r.route.dup
        @cache[_key x, y] = r_new
    end
    def has_key? x, y
        @cache.has_key? _key x, y
    end
    def size
        @cache.size
    end
    def values
        @cache.values
    end
end

def f xs, i, size
    if @cache.has_key? i, size
        @cache[i, size]
    elsif i == xs.length
        Item.new 0
    elsif size < 0
        r = f(xs, i + 1, size)
        @cache[i, size] = r
        r
    else
        x = xs[i]

        r1 =  f(xs, i + 1, size)
        r2 =  f(xs, i + 1, size - 1) + x

        r = (r1 > r2) ? r1 : r2
        @cache[i, size] = r
        r
    end
end

items = (1..100).map{|x| Item.new x * 900}
@cache = Cache.new
p f items, 0, 100
p @cache.values.to_a.select{|x| x.value <= 1000000}.sort{|x,y| -(x.value <=> y.value)}.first