Bridge Weight Limit — Minimum Drivers Turn Back

Keep a subsequence of the original queue such that, for every pair of adjacent vehicles in the kept sequence, the sum of their weights does not exceed the bridge limit U. Output the minimum number of drivers who must leave. A vehicle whose own weight exceeds U must also leave.

输入格式

The input contains U, N, and N vehicle weights. 1≤N≤100000, 1≤weight[i],U≤10^9.

输出格式

Output the minimum number of drivers who must leave.

样例 1

输入：

9
8
5 3 8 1 8 7 7 6

输出：

4

样例 2

输入：

7
8
7 6 5 2 7 4 5 4

输出：

5

样例 3

输入：

7
4
3 4 3 1

输出：

0