题目描述

小 z 和他的小伙伴们来到一个景区游玩，景区内设有 ​$n$ 个观光车站点​，编号依次为 $1, 2, ..., n$，这些站点沿着景区的主干道依次分布。游客可以在任意站点乘坐观光车，并在后面的任意站点下车。

景区规定，在站点 $i$ 上车到后面的站点 $j$ 下车（$1 \leq i < j \leq n$）需要支付车费 $a_{i,j}$。小 z 他们计划从入口站点 $1$ 出发，最终到达 ​终点站点 $n$​。

请你计算出从站点 $1$ 到游艇出租站 $n$ 所需的最少花费。

输入格式

第一行中有一个正整数 $n$，表示有 $n$ 个观光车站点。

接下来的 $n-1$ 行是一个半矩阵 $a_{i,j}$（$1\le i<j\le n$）。

输出格式

输出计算出的从站点 $1$ 到站点 $n$ 所需的最少花费。

3
5 15
7

12

5
8 25 5 33 
7 21 14 
16 13 
6

11

样例解释1: 当前在站点 $1$，首先花费 $5$ 元钱到达站点 $2$，接着花费 $7$ 元钱到达终点 $3$。

说明/提示

$1\le n\le 200,1\le a_{i,j}\le 10^6$。