Cantine X16380


Statement
 

pdf   zip

html

Every day, the UPF cantine offers a different menu. Customers can purchase any combination of items on the menu. Alice is an open-minded person that likes to mix any kind of food, and she wonders how many different combinations of menu items she can afford.

In order to pay for her meal, Alice has a restaurant ticket with total value T. There is a chance that Alice does not like any item on the menu, so one possible combination is not buying any menu item at all.

Input

The input consists of several test cases. Each test case starts with a pair of integers T < 1000 (the value of the restaurant ticket) and P < 1000 (the number of menu items). The next P numbers denote the price Pi of each menu item i, satisfying Pi < 300.

Output

For each test case, output the total number of affordable combinations.

In the first four examples, Alice can afford any of the 2P combinations.

Public test cases

  • Input

    1 1
1
2 2
1 1
3 3
1 1 1
4 4
1 1 1 1
10 4
1 2 4 6
6 5
1 1 1 3 3
8 5
9 8 4 2 1

    Output

    2
4
8
16
13
25
9
    • Information
    Author
    Javier Segovia
    Language
    English
    Official solutions
    C++
    User solutions
    C++