DWITE Online Computer Programming Contest
October 2007

Problem 4

Stacks of Blocks

Some kids play with blocks, and build things by stacking different blocks on top of each other. Given a set of blocks and a target height, we want to find out if it's possible to construct a stack with an exact specified height.

Input

The first line will contain an integer H (0 < H < 100), the target height of the stack. The second line will contain an integer S (0 < S < 10), the number of blocks in a set. The next S lines will contain one integer each. Each integer gives the height of one block in the set, which is at least 1 but less than 10. The set only contains one block of each type (see the second sample case).

Output

A single integer, the minimum number of blocks from the set required to build a stack of the requested height, or 0 if this is impossible.

Sample Input 1

5
3
1
2
3

Sample Output 1

2

Sample Input 2

10
3
1
5
7

Sample Output 2

0

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 19, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...