Coin Change

Given a set of coin denominations and a total amount, your task is to determine the minimum number of coins required to make up that amount.

If the amount cannot be achieved using the given coins, output -1.

The problem can be formulated as follows:

Given an amount \(A\) and coin denominations \(c_1, c_2, \dots, c_n\), find the minimum number of coins \(k\) such that:

\[ c_{i_1} + c_{i_2} + \cdots + c_{i_k} = A, \]

or determine that it is impossible.

inputFormat

The input is given via standard input (stdin) and has the following format:

1. The first line contains an integer m which represents the number of coin types.
2. The second line contains m space-separated integers representing the coin denominations.
3. The third line contains an integer representing the total amount to be made.

outputFormat

Output a single integer which is the minimum number of coins required to achieve the given amount. Output -1 if it is not possible to make the amount with the provided denominations.

## sample

3
1 2 5
11

3

</p>