长江游艇俱乐部在长江上设置了n个游艇出租站1,2,…,n。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1≤i<j≤n。试设计一个算法，计算出从游艇出租站1 到游艇出租站n 所需的最少租金。

数据输入：

由文件input.txt 提供输入数据。文件的第1 行中有1 个正整数n（n<=200），表示有n

个游艇出租站。接下来的n-1 行是r(i,j), 1≤i<j≤n。

结果输出:

程序运行结束时，将输出从游艇出租站1到游艇出租站n所需的最少租金。

数据文件见附件。-Yangtze River Yacht Club on the set of n Yangtze yacht rental stations 1,2, ..., n. Visitors can rent a yacht in the yacht rental stations, and the return of the yacht at any one yacht rental station downstream. Yacht rental station i to station j yacht rental rent between the r (i, j), 1≤i <j≤n. Try to design an algorithm to calculate a minimum rent　yacht rental yacht rental station 1 to station n required.

data input:

Provide input data　the file input.txt. Line 1 has a file positive integer n (n <= 200), expressed n

A yacht rental station. The next n-1 lines are r (i, j), 1≤i <j≤n.

Results output:

When the run is finished, the output　the minimum rent yacht charter yacht rental station 1 to station n required.

Data files attached.