Minimum Production Hours

Given M machines, each capable of producing a fixed number of units per hour, determine the minimum number of hours required to produce exactly T units. You may utilize any machine any number of times. Formally, for a list of production values \( P = [p_1, p_2, \dots, p_M] \) and a target \( T \), find the minimum number of hours \( h \) such that using the recurrence

\( dp[0] = 0 \) and
\( dp[i] = \min_{p \in P \;\text{and}\; i - p \ge 0} \{ dp[i - p] + 1 \} \) for \( i \ge 1 \),

we have \( dp[T] = h \).

This is analogous to the classic coin change problem but applied in the context of machine production.

inputFormat

The input consists of three lines:

• The first line contains an integer M denoting the number of machines.
• The second line contains M space-separated integers, each representing the number of units a machine can produce in one hour.
• The third line contains an integer T which is the target number of units to produce.

outputFormat

Output a single integer representing the minimum number of hours required to produce exactly T units. It is guaranteed that T is reachable using the given machines.

3
2 3 5
11

3