Given a natural number *x* and *n* different coin values *c*_{1} …
*c*_{n}, 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 *c*_{1} … *c*_{n}.
Assume 1 ≤ *n* ≤ 20,
1 ≤ *c*_{i} ≤ *x* ≤ 1000,
and that all *c*_{i} 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
- Salvador Roura
- Language
- English
- Translator
- Albert Atserias
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++