Minimum Yacht Rental Cost

The Yangtze Yacht Club has established n yacht rental stations labeled 1, 2, ... , n along the Yangtze River. Tourists can rent a yacht at any station and return it at any station downstream. The rental cost from station i to station j is given by \(r(i,j)\) for \(1 \le i < j \le n\). The task is to design an algorithm to compute the minimum rental cost to travel from station 1 to station n.

Input Format: The first line contains an integer \(n\), the number of stations. For each station \(i\) from 1 to \(n-1\), the next line contains \(n-i\) integers. The \(j\)th number on the \(i\)th line (starting count from 1) represents the rental cost \(r(i,i+j)\) from station \(i\) to station \(i+j\).

Output Format: Output a single integer representing the minimum rental cost from station 1 to station \(n\).

Note: You can assume that a valid path from station 1 to station \(n\) always exists.

inputFormat

The input begins with an integer \(n\). This is followed by \(n-1\) lines where the \(i\)th line contains \(n-i\) space-separated integers. The integer on the \(i\)th line and the \(j\)th position (with 1-based indexing) denotes \(r(i, i+j)\), the rental cost from station \(i\) to station \(i+j\).

outputFormat

Output a single integer: the minimum rental cost required to travel from station 1 to station \(n\).

sample

2
5

5