# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2018
#
# 1. 正の数しかないので頂点から下るほど数値の合計は大きくなる.
# 2. 三角形の最下段よりひとつ上から最下段へ下るとき，
#    最終的に合計が最大となるのパスを選択するには
#    現在の位置と接する右下，左下で数値の大きいパスを選択することになる．
# 3. 1と2から最下段において2つの隣り合う数値で値の小さなほうは
#    合計が最大となるパスでは選択されないことが分かり，
#    最下段で隣り合う数値の大きいほうの値をひとつの段に足すことで
#    三角形の高さを1減らすことができる．
# 以上の方法で，三角形の高さを減らしていけば，高さが1になったときの数値(頂点)は
# 通った数値の合計が最大値となるパスの合計値と一致する．

$t = %w(
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
).map{|n| n.to_i}

# 最下段のY位置．
def height
  i = 0
  ret = 0
  while (i = i.next)
    if (y_pos(i) == $t.size)
      ret = i - 1
      break
    end
  end
  ret
end
# Y位置の添え字．
def y_pos(n)
  (n <= 0) ? 0 :y_pos(n - 1) + n
end
# 高さがなくなるまで減らしていく．
(height - 1).downto(0).each do |y|
  0.upto(y) do |x|
    $t[y_pos(y) + x] += [$t[y_pos(y + 1) + x], $t[y_pos(y + 1) + x + 1]].max
  end
end
# 頂点を表示．
puts $t.shift