Problem H
Hasagi Factory

A factory of Yasuo has a robot (named NAT) to pack products into boxes. All boxes have the same capacity $W$. At any moment, there are exactly two open boxes available for the robot to use.

Each product has a volume. A box can contain a set of products as long as the sum of their volumes does not exceed the box capacity.

The products appear on a conveyor belt in a fixed order, and the robot must process them in that order. For the current product (the next unprocessed product on the conveyor), the robot may perform one of the following operations:

1. Put the current product into box 1.

2. Put the current product into box 2.

3. Close box 1 and open a new empty box as box 1.

4. Close box 2 and open a new empty box as box 2.

Operations 1 and 2 are only allowed if the product fits in the chosen box (that is, the total volume in that box does not exceed the box capacity after insertion).

Given the box capacity $W$ and the volumes of $n$ products in conveyor order $a_1, a_2, \dots , a_n$, determine the minimum number of boxes needed to pack all products.

Input

The first line contains two integers $W$ and $n$ $(1 \leq W \leq 5000,\ 1 \leq n \leq 10000)$.

The second line contains $n$ integers $a_1, a_2, \dots , a_n$ $(1 \leq a_i \leq W)$.

Output

Output a single integer: the minimum number of boxes required.

Sample 1 Explanation

An optimal packing uses exactly $3$ boxes:

1. Put $4$ into box 1.

2. Put $2$ into box 2.

3. Put $5$ into box 2 (total $7$).

4. Close box 2 and open a new empty box as box 2.

5. Put $3$ into the new box 2.

6. Put $5$ into the new box 2 (total $8$).

7. Put the last $4$ into box 1 (total $8$).

Thus, a total of $3$ boxes are used:

8 6
4 2 5 3 5 4

3

12 6
6 9 6 9 6 9

5