题目描述

输入格式

第一行输入一个正整数n（2≤n≤200），表示出租站数量。 接下来n-1行输入一个半矩阵r[i][j]（1≤i<j≤n）： •第1行包含r[1][2], r[1][3], ..., r[1][n]（共n-1个值）； •第2行包含r[2][3], r[2][4], ..., r[2][n]（共n-2个值）； •...以此类推，第n-1行无数据（因i<j不成立）。 租金r[i][j]为正整数，范围[1, 1000]。

输出格式

输出一行整数，表示从站1到站n最多换乘一次的最少租金。

样例

样例 1

输入 # 1

4
5 10 15
3 6
4

输出 # 1

11