提示: 欢迎访问OurACM平台。
Problem 1436 Renting Boats

Accept: 334    Submit: 708
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Yangtse Rive Barge Club has set up n barge hiring stops numbered 1, 2, … , n along the Changjiang River. Passengers can hire barges from any of these stops, and return the barges to one of the stops afterward. The rent for an barge from stop i to stop j is r(i,j) (1<=i,j<=n). Your task is to design an algorithm to minimize the rent of hiring barges when you traveling from stop 1 to stop n.

Input

There are multiple test cases. The first line of each case contains an integer n indicating the number of the stops (n<=200). The following n-1 lines are the rent between any two stops. The ith following line contains n-i integers indicating r(i,j) (i < j <= n).

Output

For each case, output one line representing the minimal rent.

Sample Input

3 5 15 7

Sample Output

12

Source

FZU 2006 Summer Training II

Submit  Back  Status  Discuss