Disclaimer

The intended solution gets TLE in Python3, but it has been confirmed to get AC when submitted in PyPy3.

Problem Statement

Rian-kun is a descendant of ninja and is able to create clones of himself.

Today Rian-kun is participating in a programming contest, and after some thinking, he has figured out the solutions to all the problems and the time needed to code each of them. However, he spent so much time thinking that only $T$ minutes remain for coding.

So he has decided to use his specialty, cloning, to code in parallel. However, both cloning and preparing a PC for each person cost something, so he wants to keep the number of clones as small as possible.

Therefore, find the minimum number of clones required to solve all the problems within the time limit (that is, how many people coding in parallel are needed to solve all the problems in time).

Note that code cannot be copied and pasted between PCs, so each problem must not be split across multiple PCs and must be written entirely on one PC.

Input

$T$
$N$
$t_1$
:
$t_N$

The first line gives the remaining contest time $T$.

The second line gives the number of problems $N$.

In the following $N$ lines, starting from the third line, the time $t_i$ needed to implement the $i$-th problem is given.

All input values are integers and satisfy the following constraints.

• $1 \le T \le 2000$
• $1 \le N \le 17$
• $1 \le t_i \le T$

Output

Output the minimum number of clones required to solve all the problems within the time limit.

Print a newline at the end.

Sample

5
3
1
5
3

2

9
4
5
5
5
5

4

10
6
2
2
2
3
5
6

2