题目描述

给出一个含 $n$ 项的数列。请将数列划分成若干段，要求每个数都属于且只属于一段，每一段都是原数列中连续的一段。

每一段的元素和的绝对值都必须不超过 $k$。最多能划分成多少段？

例如，对于数列 $-2,2,-9,-3,8,3$，$k=2$。划分为 $[-2,2]$ 和 $[-9,-3,8,3]$ 符合要求：两段元素和的绝对值分别为 $0$ 和 $1$，均不超过 $2$。

输入格式

第一行，两个正整数 $n,k$。

第二行，$n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出最多能划分成的段数。如果无法划分，输出 $-1$。

输入输出样例

输入 #1

6 2
-2 2 -9 -3 8 3

输出 #1

3

数据范围

• 对于 $30\%$ 的数据，$n\le 20$；
• 对于全部数据，$1\le n\le 2000$，$0\le k\le 10^6$，$-10^6\le a_i\le 10^6$。

1 85
-19

1

1 86
-99

-1

6 2
-2 2 -9 -3 8 3

3