Untitled

Sum it up
Level 4
Sum it up
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.

 

Input

The input file will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers x1, . . . ,xn. t will be a positive integer less than 1000, n will be an integer between 1 and 12 (inclusive), and x1, . . . , xn will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list may be repetitions.

 

Output

For each test case, output the total way, if not output -1.

 

Sample

Input

4

4 6

4 3 2 2 1 1

5 3

2 1 1

400 12

50 50 50 50 50 50 25 25 25 25 25 25

20 10

1 2 3 4 5 6 7 8 9 10

 

Output

#1 4

#2 -1

#3 2

#4 31

20
644 12
54 80 97 20 47 98 68 28 25 55 2 70 
498 12
60 70 15 4 32 44 93 37 21 25 38 59 
150 12
9 93 72 64 9 27 47 24 3 26 75 3 
499 11
57 33 43 12 42 35 8 61 49 73 86 
734 11
55 89 23 28 81 58 90 77 72 64 97 
302 12
61 100 72 28 7 26 18 60 70 61 62 39 
295 11
82 31 72 46 97 98 61 13 17 47 26 
201 10
62 63 2 46 39 95 71 58 69 99 
133 10
66 55 48 89 28 83 18 20 100 28 
272 11
55 24 43 94 38 78 68 3 25 94 22 
171 12
35 54 64 67 29 13 81 26 3 43 58 40 
207 12
49 73 4 62 18 40 95 69 35 33 96 49 
429 10
53 25 60 30 36 35 15 100 69 6 
226 10
68 51 75 64 13 75 85 96 60 92 
626 12
45 65 11 81 40 80 83 21 60 65 28 47 
407 12
79 96 81 82 42 45 89 90 88 72 38 13 
152 12
80 51 59 94 35 63 15 14 89 18 68 25 
350 12
1 73 75 58 86 64 49 52 88 60 45 49 
261 10
38 90 71 16 33 82 36 91 42 23 
692 10
100 87 93 69 29 53 62 76 50 73