|
Лимит времени 1500/2000/2000/2000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Игорь Андрианов, ВоГТУ.
Monetary system in Byteland contains of N kinds of coins of different
denominations. During ATM software developing, there occured a problem to give
out the requested sum with minimal quantity of coins. To solve it, the
following greedy algorithm was introduced. At first, maximal quantity of coins
of greatest denomination are taken. Then, for the remaining sum, maximal
quantity of coins of lesser denomination (next one in descending order)
are taken, and so forth.
|
For example, we have coins of denominations 1, 2 and 5. To pay sum of 13,
two coins of 5 are taken, then one coin of 2 and then one coin of 1 are taken.
Your task is to define, if this algorithm works correctly in all cases for
a given monetary system.
Input
The first line of the input contains N (1 ≤ N ≤ 1000).
The second line contains N coin denominations in ascending order,
separated by single spaces (1 ≤ Di ≤ 1000).
The first denomination is always 1.
Output
If the introduced algorithm really gives out any sum with minimal quantity
of coins, output 0. Otherwise output the minimal sum, that the algorithm
will give out with non-minimal quantity of coins.
|
|
Input 1
|
Output 1
|
3
1 2 5
|
0
|
|
Input 2
|
Output 2
|
4
1 3 4 5
|
7
|
|
Для отправки решений необходимо выполнить вход.
|