購物中心最近大特價,你決定把每家店的商品都買一遍。購物中心是一個長型的建築,每隔一公尺就會有一個店家,由左至右編號為 1, 2, …, n。入口在這個購物中心的最左邊與第一個店家相距 1 公尺;而且你事先得知編號為 i 的店家每 Ti 秒會補一次貨,你需要在店家補貨時到達店家門口才來的及搶購商品。現在你好奇,最快可以在多少時間內把每家店的商品都買一遍。
假定你的體力很好,隨時以每秒 1 公尺的速度移動,並且不受移動方向改變的影響,買東西所花的時間也可以忽略不計。
第一行有一個數字 n,代表商店的數量 (1≤n≤16)。 第二行有 n 個數字。所有數字皆不大於 108。
請輸出結束所需的最少秒數。
TIOJ 1014