TopCoder

User's AC Ratio

96.6% (57/59)

Submission's AC Ratio

53.0% (88/166)

Description

隨著時間的腳步前進,打地鼠遊戲也不斷的翻新,最新一代的打地鼠遊戲不只測試你的反應能力,同時也考驗著你的體力和智力。地鼠基地是一個長型的基座,基座上每隔一公尺就會有一個地鼠洞,由左至右編號為 $1, 2, \cdots, n$。玩家站在這個基地的最左邊,與第一個地鼠洞相距1公尺;拿著一根鎚子,準備開始這個遊戲。編號為 $i$ 的地鼠洞每 $T_i$ 秒地鼠會出現一次。被打的地鼠不再出現,只要將所有地鼠打完,就結束遊戲,並且紀錄從開始到結束遊戲的秒數,越快越好。現在問題來了,負責製造這個地鼠基地的遊戲廠商想要知道結束遊戲所需的最少秒數,於是拜託你幫忙寫個程式來解決它。

假定玩家們的體力很好,隨時以每秒1公尺的速度移動,並且不受移動方向改變的影響,打地鼠所花的時間也可以忽略不計。

Input Format

第一行有一個數字 $n$,代表地鼠洞的數量 $(1\le n\le 16)$。第二行有 $n$ 個數字。所有數字皆不大於 $100,000,000$。

Output Format

請輸出結束遊戲所需的最少秒數 $S$。

Sample Input

3
3 2 5

Sample Output

5

Hints

Problem Source

原TIOJ1014 / 95建中資訊培訓模擬試題一(Prob 6)

Subtasks

For Testdata: 0 ~ 0, Score: 12
For Testdata: 1 ~ 1, Score: 12
For Testdata: 2 ~ 2, Score: 12
For Testdata: 3 ~ 3, Score: 12
For Testdata: 4 ~ 4, Score: 12
For Testdata: 5 ~ 5, Score: 12
For Testdata: 6 ~ 6, Score: 12
For Testdata: 7 ~ 7, Score: 16
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536