Minimum Coins Change Problem

You are given a set of coin denominations and a target value. Your task is to compute the minimum number of coins required to make exactly the target amount. If it is impossible to form the target amount using any combination of the given coins, output -1.

In other words, given a list of integers \(coins = [c_1, c_2, \dots, c_n]\) and a target amount \(T\), you need to determine the minimum number of coins needed such that their sum is \(T\). The result should be \(-1\) if no such combination exists.

The problem can be formally modeled as follows:

Find \(dp[T]\) where \[ \begin{aligned} dp[0] &= 0, \\ dp[i] &= \min_{coin \in coins,\, coin \leq i} (dp[i - coin] + 1) \quad \text{for } i \ge 1. \end{aligned} \]

inputFormat

The input is provided via standard input and has the following format:

• The first line contains a single integer \(n\) representing the number of coin denominations.
• The second line contains \(n\) space-separated integers representing the coin denominations.
• The third line contains a single integer representing the target amount \(T\).

outputFormat

Output a single line with one integer: the minimum number of coins required to form the target amount \(T\). If it is not possible, output -1.

3
1 3 4
6

2