A tower of tables.

Tiger's engineering professor has given a surprise test to the entire class! For this test, students are given some tables and are required to build a tower using those tables.

The tower can be formed by stacking a table onto two other tables. If tables are viewed length-wise, 2 legs of the table are on one table below and the other 2 legs are on the other table below.

Each table has a weight of $K$. The apparent weight is the amount of force required to lift the table. The four legs of the table evenly distribute the apparent weight onto some surfaces below.

Many of the $N$ available tables are questionable, so the $i^{\text{th}}$ table can only support an apparent weight of $t_i$ from the table legs above before collapsing.

Tiger wants to build the highest table tower that he can to impress his professor and the other students. Can you help him determine what that height will be?

Constraints

For all subtasks:

$1\le K\le {10}^{15}$

$1\le N\le 2000$

$1\le t_i\le {10}^{18}$

Subtask 1 [10%]

All values of $t_i$ are the same.

Subtask 2 [15%]

$t_i=i$

Subtask 3 [15%]

$N\le 10$

Subtask 4 [10%]

$N\le 20$

Subtask 5 [50%]

No additional constraints.

Input Specification

The first line contains $K$.

The next line contains the integer $N$.

The following line contains $N$ space-separated integers. The $i^{\text{th}}$ integer is $t_i$.

It is guaranteed that in any non-collapsing tower, a table's apparent weight is always an integer.

Output Specification

The maximum height of a table tower. This is the number of layers in the largest table tower.

Sample Input

102
3
51 1 51

Sample Output

2