← 返回题目列表

Codeforces · 10/E

E. 贪婪的改变

中文机器翻译题面 查看原题

比利研究了将贪婪算法应用于生活不同领域的问题。目前他正在研究贪心算法在变化问题中的应用。不同面值的硬币数量为n枚,每种面值的硬币数量不限。任务是用最少数量的硬币收集总和x。贪心算法的每一步都取面值最高的硬币,不超过x。显然,如果硬币的面值中存在面值1,则通过贪心算法可以得到任意的和x。然而,贪心算法并不总是给出总和的最佳表示,即用最少的硬币数量表示。例如,如果有面值{1,3,4},要求收集总和为6,贪心算法会将总和表示为4+1+1,而最佳表示为3+3,少包含一枚硬币。通过给定的一组面值,找出是否存在贪心算法会以非最佳方式收集的总和 x。如果存在这样的和,找出这些和中最小的一个。

输入

第一行包含一个整数 n (1 ≤ n ≤ 400) — 硬币面值的数量。第二行包含n个整数ai(1≤ai≤109),描述面值。保证 a1 > a2 > ... > an 且 an = 1。

输出

如果贪心算法以最优方式收集任意总和,则输出 -1。否则输出贪心算法以非最优方式收集到的最小总和。

示例

输入 #1

5
25 10 5 2 1

输出 #1

-1

输入 #2

3
4 3 1

输出 #2

6