Dues monedes de cada (3) X92609

Statement

html

Donat un nombre x i n valors diferents de monedes m₁ …m_n, de quantes maneres es pot aconseguir canvi x usant cada valor com a molt dues vegades? Considereu iguals dues monedes amb el mateix valor.

Per exemple, si x = 4 i disposem dels valors 1 i 2, tenim dues maneres: 1 + 1 + 2 i 2 + 2. Com un altre exemple, si x = 5 i disposem dels valors 1, 2, 3, 4 i 5, tenim cinc maneres: 1 + 1 + 3, 1 + 2 + 2, 1 + 4, 2 + 3 i 5.

Entrada

L’entrada consisteix en diversos casos, només amb nombres enters. Cada cas comença amb x i n, seguit de m₁ …m_n. Suposeu 1 ≤ n ≤ 15, 1 ≤ m_i ≤ x ≤ 10⁶, i que totes les m_i són diferents.

Sortida

Per a cada cas, escriviu el nombre de maneres diferents d’aconseguir canvi exactament x usant cada valor com a molt dues vegades.

Pista

Un backtracking mitjanament espurgat hauria de ser suficient.

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

Information

Author: Salvador Roura
Language: Catalan
Other languages: English
Official solutions: Unknown. This problem is being checked.
User solutions: C++