Minimum Coins Collection

You are given N distinct types of coins with values represented by an array. Your task is to determine the minimum number of coins required to achieve exactly a target sum C. However, there is a twist: the beggar can carry at most K coins at a time. In other words, if the minimum number of coins needed exceeds K, then the answer is considered impossible and you should return -1.

The problem can be modeled as a variation of the classic coin change problem where you need to satisfy the capacity constraint:

$$\textbf{dp}[0]=0\quad \text{and} \quad \textbf{dp}[x]=\min_{\text{coin}\;\in\;\text{coins}}\{\textbf{dp}[x-\text{coin}]+1\}\;\text{for}\; x\geq \text{coin}.$$

If \(\textbf{dp}[C]\) is more than \(K\) or remains infinite (i.e. it is impossible to form \(C\)), output -1.

inputFormat

The first three space-separated integers are:

• N — the number of distinct coin types.
• C — the target coin sum.
• K — the maximum number of coins that can be carried at once.

Following that, there are N integers representing the value of each coin type. All input is given through standard input (stdin).

outputFormat

Output a single integer on standard output (stdout): the minimum number of coins required to collect exactly C coin sum if the number does not exceed K; otherwise, output -1.

4 12 3 1 5 7 10

2