TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

77.8% (14/18)

Submission's AC Ratio

28.6% (20/70)

Description

  在第501統合戦闘航空団裡,你是一個傳令兵隊的隊長(在傳訊系統的最上層),你要負責將只令下達下去,你們的團隊有種非常特別的傳訊方式(如圖上的方式)。

  圖上的數字則代表回到崗位的時間,而箭頭則代表傳訊的方向。

  而傳令的條件如下:

   1.傳令時必須兩個人都在工作崗位上

   2.傳令需要花費一單位的時間

  現在你知道有n(n+1)/2個人(n層傳輸層),以及每個人回到崗位的時間,最快要讓所有人知道訊息需要多久?

Input Format

本題有多筆測試資料,以EOF為結束

每筆測試資料的

第一行有一個數字n,代表有n個傳輸層(1<=n<=100)

第二行開始有n行,第i行共有i個數字以空白隔開,代表該人回到崗位的時間T(1<=T<=50)

Output Format

對每筆資料輸出一個數字k,代表最少要花k單位的時間才能讓所有人知道訊息

Sample Input

3
1
9 9
1 2 3

Sample Output

11

Hints

Problem Source

原TIOJ1391 / 快樂暑假營第三次練習比賽。
Problem Setter:hallogameboy

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2