|
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
|
|