Minimum Coins Problem

You are given a set of distinct coin denominations and a target amount of money \(A\). Your task is to find the minimum number of coins required to form the amount \(A\) using the given denominations. If it is not possible to form \(A\) with the provided coins, your program should output \(-1\).

The problem can be formalized as follows:

Given a list of coin denominations \(\{c_1, c_2, \dots, c_n\}\) and an amount \(A\), determine the minimum number \(m\) such that there exists a combination of coins with replacement where:

[ \sum_{i=1}^{m} coin_i = A ]

If no such combination exists, return \(-1\).

inputFormat

The input is read from standard input and consists of two lines:

• The first line contains the coin denominations separated by spaces. For example: 1 2 5
• The second line contains a single integer representing the target amount.

For example:

1 2 5
11

outputFormat

Output a single integer which is the minimum number of coins needed to form the target amount. If it is not possible to form the amount, output -1.

For example:

3

## sample

1 2 5
11

3