Two coins of each kind (3) X92609


Statement
 

pdf   zip

html

Given a number x and n different coin values c1 … cn, 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 equal.

For example, if x = 4 and the available values are 1 and 2, then there are two ways to achieve it: 1 + 1 + 2 and 2 + 2. As another example, if x = 5 and the available values are 1, 2, 3, 4 and 5, then there are five ways: 1 + 1 + 3, 1 + 2 + 2, 1 + 4, 2 + 3 and 5.

Input

Input consists of several cases, with only integer numbers. Every case begins with x and n, followed by c1 … cn. Assume 1 ≤ n ≤ 15, 1 ≤ ci ≤ x ≤ 106, and that all ci are different.

Output

For every case print the number of different ways to achieve change exactly x by using each value at most twice.

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

    2
1
0
2
5
    • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Albert Atserias
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++