Minimum Coins

You are given a set of coin denominations and a target value. Your task is to determine the minimum number of coins required to sum exactly to the target value using the available coin denominations. If it is not possible to form the target with the given coins, output -1. This problem can be solved efficiently using dynamic programming.

The solution should handle a variety of cases including exact target formation, impossible combinations, and edge cases such as a target of zero.

Formally, given coin denominations \(c_1, c_2, \dots, c_n\) and a target \(T\), you need to compute the minimum number of coins such that \(\sum_{i=1}^{k} c_{j_i} = T\). If no such combination exists, output \(-1\).

inputFormat

The input is provided via standard input (stdin) in the following format:

• The first line contains an integer \(N\), representing the number of coin denominations.
• The second line contains \(N\) space-separated integers, representing the coin denominations.
• The third line contains an integer \(T\), representing the target sum.

outputFormat

The output should be printed to standard output (stdout) and must consist of a single integer: the minimum number of coins required to form the target sum. If it is impossible to obtain the target sum using the given coins, print \(-1\).

## sample

3
1 2 5
11

3

</p>