# in Introduction to Algorithms
# Chapter 15, Dynamic Programming, p.329
#
INT_MAX = 2**32

$stations = [
   [7, 9, 3, 4, 8, 4],
   [8, 5, 6, 4, 5, 7]]

$enters = [2, 4]
$exits = [3, 2]
$crosses = [
   [2, 3, 1, 3, 4],
   [2, 1, 2, 2, 1]]

$states = [
   Array.new($stations[0].size, INT_MAX),
   Array.new($stations[1].size, INT_MAX)]

def fastest_way
   2.times { |i| $states[i][0] = $enters[i] + $stations[i][0] }

   1.upto($stations[0].size-1).each do |i|
      # for line 0
      2.times do |j|
         $states[0][i] = [$states[0][i], $states[0][i-1] + $stations[0][i]].min                    # for 0->0
         $states[0][i] = [$states[0][i], $states[1][i-1] + $stations[0][i] + $crosses[1][i-1]].min # for 1->0
      end

      # for line 1
      2.times do |j|
         $states[1][i] = [$states[1][i], $states[1][i-1] + $stations[1][i]].min                    # for 1->1
         $states[1][i] = [$states[1][i], $states[0][i-1] + $stations[1][i] + $crosses[0][i-1]].min # for 0->1
      end
   end
   [$states[0].last + $exits[0],
    $states[1].last + $exits[1]].min

end

p fastest_way