Description

The Yangtze River Yacht Club has set up $n$ yacht rental stations $1,2,\dots,n$ along the Yangtze River. Tourists can rent a yacht at any of these stations and return it at any downstream station. The rent between yacht rental station $i$ and yacht rental station $j$ is $r_{i,j}$ ($1\le i\lt j\le n$). Design an algorithm to compute the minimum total rent needed to travel from yacht rental station $1$ to yacht rental station $n$.

Input Format

The first line contains a positive integer $n$, indicating there are $n$ yacht rental stations.
The next $n-1$ lines give a half matrix $r_{i,j}$ ($1\le i<j\le n$): for each $i$ from $1$ to $n-1$, the $i$-th of these lines contains $n-i$ integers $r_{i,i+1}, r_{i,i+2}, \dots, r_{i,n}$.

Output Format

Output the minimum total rent required to travel from yacht rental station $1$ to yacht rental station $n$.

3
5 15
7

12

Hint

$1\le n\le 200$, and it is guaranteed that at any time during the computation, all numbers do not exceed $10^6$.

Translated by ChatGPT 5