Taco Combination Count

You are given a set of N different prices of items and a target amount S. Your task is to determine the number of distinct ways to exactly spend exactly S by choosing any number of items from the given prices (each item can be chosen an unlimited number of times). Two ways are considered distinct if the counts of at least one selected price differ.

The problem can be formulated using a dynamic programming approach. Let \(dp[i]\) denote the number of ways to get a sum of \(i\) using the prices. The base case is \(dp[0] = 1\) (there is exactly one way, by choosing nothing). For each price \(p\) and for each value from \(p\) to \(S\), you can update:

[ dp[j] = dp[j] + dp[j-p] \quad for ; j = p, p+1, \dots, S. ]

Compute \(dp[S]\) to obtain the answer.

inputFormat

The input is given via standard input (stdin) and consists of three lines:

• The first line contains an integer \(N\): the number of different prices.
• The second line contains \(N\) space-separated positive integers representing the prices.
• The third line contains an integer \(S\): the exact amount to be spent.

outputFormat

Output a single integer via standard output (stdout), which is the number of distinct ways to spend exactly \(S\) using the provided prices.

3
1 2 3
4

4