Minimum Elements to Sum

You are given an array of integers and a target sum. Your task is to determine the minimum number of elements required (elements may be used repeatedly) to exactly form the target sum. If it is not possible to obtain the target sum by any combination of the elements, output -1.

In other words, let \(dp[i]\) denote the minimum number of elements needed to sum to \(i\). Then, the recurrence is given by:

[ dp[i] = \min_{a \in A,; i - a \ge 0}{ dp[i - a] + 1 } ]

with the base case \(dp[0] = 0\). If \(dp[target]\) remains infinite (or a very large number) then the answer is -1.

inputFormat

The first line of input contains a single integer \(n\), denoting the size of the array. The second line contains \(n\) space-separated integers representing the elements of the array. The third line contains a single integer \(target\), the sum to achieve.

outputFormat

Output a single integer representing the minimum number of elements needed to form the target sum using the elements of the array (each element can be used multiple times). If it is not possible, output -1.

3
1 2 3
6

2