题目背景

dl24jp周围交通便利

许多学生和老师选择乘坐快轨出行

某位认真负责的老师在快轨上批改作业的情景被记录了下来

令人感动 心生敬意 成为美谈

题目描述

大连市快轨沿线设置了 $n$ 个车站 $1,2,\cdots,n$。乘客可在这些车站上车，并在接下来的任何一个车站下车。车站 $i$ 到车站 $j$ 之间的票价为 $a(i,j)$（$1\le i\lt j\le n$）。

现在 老师想从1号车站坐快轨到达dl24jp附近的n号车站。

但他忙于批改作业无法计算票价。

所以请你帮老师计算一下最少的票价。

注：票价与现实中并不相同 并不是乘坐的站数越多越划算 这是虚拟的场景 请不要百度搜索票价并代入计算！

输入格式

第一行中有一个正整数 $n$，表示有 $n$ 个快轨车站。接下来的 $n-1$ 行，第 $i$ 行有 $n-i$ 个数 , 第 $i$ 行的第 $j$ 个数表示从 $i$ 号车站到 $i+j$ 号车站的票价是多少。

比如样例$1$ 第一行的 $3$ 表示有 $3$ 个车站

从第二行开始

第一行的第一个数 $5$ 表示从第 $1$ 个车站到第 $2$ 号车站的票价为 $5$

输出格式

一个数表示从车站 $1$ 到车站 $n$ 所需的最少票价。

样例

3
5 13
6

11

数据范围与约定

对于 $40\%$ 的数据 保证 $n\le 40$

对于 $100\%$ 的数据 保证 $n\le 200$，计算过程中任何时刻数值都不超过 $10^9$。

提示

请仔细阅读输入格式 结合样例理解题意！

请留意本题时间限制与内存空间限制。

程序运行超时将导致部分测试点 TLE 而损失部分分， 数组开得太大将导致所有测试点 MLE 而损失所有分。 建议数组总长度不超过 $10^6$ (如 int a[10000][10000] / int a[100000000] 等定义将导致你获得 0 分的超高分)

本题使用文件输入输出！！！