Description 長江游艇俱樂部在長江上設(shè)置了n 個游艇出租站1，2，…，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個游艇出租站歸還游艇。游艇出租站i 到游艇出租站j 之間的租金為r(i,j),1≤i＜j≤n。試設(shè)計一個算法，計算出從游艇出租站1 到游艇出租站n 所需的最少租金。 編程任務： 對于給定的游艇出租站i 到游艇出租站j 之間的租金為r(i,j),1≤i＜j≤n，編程計算從游艇出租站1 到游艇出租站n所需的最少租金。 Input 輸入由多組測試數(shù)據(jù)組成。 每組測試數(shù)據(jù)輸入的第1 行中有1 個正整數(shù)n（n≤200），表示有n個游艇出租站。接下來的n-1 行是r(i,j),1≤i＜j≤n。 Output 對應每組輸入，輸出的每行是計算出的從游艇出租站1 到游艇出租站n所需的最少租金。 Sample Input 3 5 15 7 Sample Output 12