# -*- coding: utf-8 -*-
require 'csv'

$matrix = []
CSV.foreach("matrix.txt") {|row|
  $matrix << row.map(&:to_i)
}

$transposed_matrix = $matrix.transpose # 転置行列

$memo = Array.new($matrix.size) { Array.new($matrix.size, nil) }

def solv
  (0...$matrix.size).each {|i|
    $memo[i][0] = $matrix[i][0]
  }
  (1...$matrix.size).each {|j|
    (0...$matrix.size).each {|i|
      arr = []
      (0...$matrix.size).each {|ii|
        arr << $memo[ii][j-1] + if ii < i
                                  $transposed_matrix[j][ii..i].reduce(:+)
                                elsif ii == i
                                  $transposed_matrix[j][ii]
                                else
                                  $transposed_matrix[j][i..ii].reduce(:+)
                                end
      }
      $memo[i][j] = arr.min
    }
  }
end

solv
p $memo.transpose[-1].min