玲珑塔

题目描述

话说孙悟空被托塔天王的玲珑塔罩住，但是以孙悟空的本事这塔根本困不住他，玲珑塔有 $n$ 层，塔内有层层封印，格子里的数字表示封印的数量，悟空可以从塔底选择一个格子，沿着箭头向塔顶走，然后从塔顶出去，问悟空出塔需要破除最少的封印数是多少。

输入格式

第一行输入一个整数 $n$，表示塔的高度。

第二行到第 $n+1$ 行的整数表示宝塔的封印，第 $i$ 行有 $i-1$ 个整数 $k$。

输出格式

一个整数，表示破除的最少封印数量。

样例输入 #1

4
5
10 2
4 11 13
15 12 14 16

样例输出 #1

30

数据范围

$1 \le n \le 30$，$0 \le k \le 100$

知识点与难度

本题涉及的知识点从属于 GESP六级（动态规划、数字三角形 DP），难度等级：⭐⭐⭐。

测试点分布