# Two coins of each kind (1) P62113

Statement html

Given a natural number x and n different coin values c1cn, compute in how many ways it is possible to achieve change x by using each value at most twice. Here, two coins with the same value are considered different.

For example, if x = 4 and the available values are 1 and 2, then there are three ways to achieve it: 1 + 1′ + 2, 1 + 1′ + 2′, and also 2 + 2′.

Input

Input consists of several cases. Every case begins with x and n, followed by c1cn. Assume 1 ≤ n ≤ 20, 1 ≤ cix ≤ 1000, and that all ci are different.

Output

For every case print, in lexicographic order, all possible ways to exactly achieve change x by using each value at most twice. Print every solution with its values sorted from small to big. In doing that, assume 1 < 1′ < 2 < 2′ < …. Use “1p” to print 1′, etcetera. Print a line with 10 dashes at the end of every case.

Hint

A simply pruned backtracking should be enough.

Public test cases
• Input

```4 2  1 2
400 1  200
400 1  300
5 3  4 2 1
5 5  1 2 3 4 5
```

Output

```4 = 1 + 1p + 2
4 = 1 + 1p + 2p
4 = 2 + 2p
----------
400 = 200 + 200p
----------
----------
5 = 1 + 2 + 2p
5 = 1 + 4
5 = 1 + 4p
5 = 1p + 2 + 2p
5 = 1p + 4
5 = 1p + 4p
----------
5 = 1 + 1p + 3
5 = 1 + 1p + 3p
5 = 1 + 2 + 2p
5 = 1 + 4
5 = 1 + 4p
5 = 1p + 2 + 2p
5 = 1p + 4
5 = 1p + 4p
5 = 2 + 3
5 = 2 + 3p
5 = 2p + 3
5 = 2p + 3p
5 = 5
5 = 5p
----------
```
• Information
Author