Minimum Cars to Remove

Cars enter the bridge in their original order; when one leaves, the next enters, so at most two adjacent cars are on the bridge at a time. Cars may be removed in advance, and the remaining cars keep their relative order. Find the minimum number of removals so that the total weight never exceeds the capacity. A single car may not exceed the capacity either.

This site uses a standard input/output protocol.

输入格式

The first line contains N capacity, and the second line contains N weights. N is 1..100000 and the weights are 1..10⁹; the source gives no bound on the capacity, and this site uses 1..2×10⁹.

输出格式

Output a single integer, the answer.

样例 1

输入：

5 8
3 5 2 6 1

输出：

0

样例 2

输入：

5 8
3 7 2 6 1

输出：

1

样例 3

输入：

3 4
9 2 2

输出：

1

样例说明

Example 1: every adjacent sum is ≤8, so remove 0. Example 2: after removing 7, the cars 3, 2, 6, 1 are all compatible, so remove 1. Example 3: 9 alone exceeds the capacity; after removing it, 2+2 is exactly 4, so remove 1.