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