Subset Sum with Sticks

Given an integer \(x\) and a list of \(n\) stick lengths, determine whether there exists a subset of these sticks whose sum is exactly \(x\). In this problem, the empty subset is considered to have a sum of \(0\). Use dynamic programming to solve the problem efficiently. For example, if \(x=10\) and the stick lengths are [1,2,3,4,5,6], one possible subset [4,6] sums to 10.

Note: The solution should read input from standard input (stdin) and write the answer to standard output (stdout). The answer must be output as either true or false (all lowercase) depending on whether such a subset exists.

inputFormat

The input is given in the following format:

1. The first line contains an integer \(x\), the target sum.
2. The second line contains an integer \(n\), representing the number of sticks.
3. The third line contains \(n\) space-separated integers, each representing the length of a stick.

outputFormat

Output a single line containing true if there exists a subset of the given sticks that sums to exactly \(x\), otherwise output false.

10
6
1 2 3 4 5 6

true