TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

購物中心最近大特價,你決定把每家店的商品都買一遍。購物中心是一個長型的建築,每隔一公尺就會有一個店家,由左至右編號為 $1,\ 2,\ \dots,\ n$。入口在這個購物中心的最左邊與第一個店家相距 $1$ 公尺;而且你事先得知編號為 $i$ 的店家每 $T_i$ 秒會補一次貨,你需要在店家補貨時到達店家門口才來的及搶購商品。現在你好奇,最快可以在多少時間內把每家店的商品都買一遍。

假定你的體力很好,隨時以每秒 $1$ 公尺的速度移動,並且不受移動方向改變的影響,買東西所花的時間也可以忽略不計。

Input Format

第一行有一個數字 $n$,代表商店的數量 ($1\le n\le16$)。
第二行有 $n$ 個數字。所有數字皆不大於 $10^ 8$。

Output Format

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

Sample Input 1

3
3 2 5

Sample Output 1

5

Hints

Problem Source

TIOJ 1014

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~24 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 524288 65536 1 2
1 500 524288 65536 2
2 500 524288 65536 2
3 500 524288 65536 2
4 500 524288 65536 2
5 500 524288 65536 2
6 500 524288 65536 2
7 500 524288 65536 2
8 500 524288 65536 2
9 500 524288 65536 2
10 500 524288 65536 2
11 500 524288 65536 2
12 500 524288 65536 2
13 500 524288 65536 2
14 500 524288 65536 2
15 500 524288 65536 2
16 500 524288 65536 2
17 500 524288 65536 2
18 500 524288 65536 2
19 500 524288 65536 2
20 500 524288 65536 2
21 500 524288 65536 2
22 500 524288 65536 2
23 500 524288 65536 2
24 500 524288 65536 2