Minimum Coin Change

Given four coin denominations (A), (B), (C), and (D), determine the minimum number of coins required to form exactly the target sum (S). You may use each coin an unlimited number of times. If it is impossible to form the sum (S) using the provided coins, output (-1).

The problem can be approached using dynamic programming. Define (dp[x]) as the minimum number of coins needed to form the value (x), with the recurrence: [ \begin{aligned} dp[0] &= 0, \ dp[x] &= \min_{coin\in{A,B,C,D}} {dp[x-coin]+1} \quad \text{for } x \geq \min{A,B,C,D}, \end{aligned} ] and set (dp[x] = \infty) if (x) cannot be formed. The final answer is (dp[S]) if it is finite, otherwise (-1).

inputFormat

Input is given in a single line containing five space-separated integers: (A), (B), (C), (D), and (S).

outputFormat

Output a single integer representing the minimum number of coins needed to form (S), or (-1) if it is impossible.## sample

1 3 4 5 7

2