TopCoder

User's AC Ratio

41.2% (7/17)

Submission's AC Ratio

11.0% (8/73)

Description

自從打地鼠遊戲在TIOJ上掀起一陣旋風(詳見TIOJ 1014),路上到處都看得到最新一代的打地鼠遊戲機所造成的哀鴻遍野(耗費太多體力以及腦力造成身體不堪負荷)。

但,時代創造英雄,英雄創造時代,在這一片慘悽悽的風風雨雨中,終究會造就出新一代的地鼠王,他會是你嗎?

地鼠基地是一個長型的基座,基座上每隔一公尺就會有一個地鼠洞,由左至右編號為1,2,...,n。玩家站在這個基地的最左邊,與第一個地鼠洞相距1公尺;拿著一根鎚子,準備開始這個遊戲。編號為 i 的地鼠洞每T_i 秒地鼠會出現一次。被打的地鼠不再出現,只要將所有地鼠打完,就結束遊戲,並且紀錄從開始到結束遊戲的秒數,越快越好。現在問題來了,負責製造這個地鼠基地的遊戲廠商想要知道結束遊戲所需的最少秒數,於是拜託你幫忙寫個程式來解決它。

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

Input Format

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

Output Format

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

Sample Input

3
3 2 5

Sample Output

5

Hints

Problem Source

原TIOJ1261 / 全民暴搜大賽(prob D)。Problem Setter:hallogameboy。

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 5
For Testdata: 18 ~ 18, Score: 5
For Testdata: 19 ~ 19, Score: 5
No. Time Limit (ms) Memory Limit (KiB)
0 1500 65536
1 1500 65536
2 1500 65536
3 1500 65536
4 1500 65536
5 1500 65536
6 1500 65536
7 1500 65536
8 1500 65536
9 1500 65536
10 1500 65536
11 1500 65536
12 1500 65536
13 1500 65536
14 1500 65536
15 1500 65536
16 1500 65536
17 1500 65536
18 2500 65536
19 3500 65536