题目描述

为了更好地观察实验结果，需要将进行实验的原子序列分配到若干台仪器上进行检测，用于观察和辨识不同类型的原子。每个原子携带的电子数用一个整数表示。在仪器工作时，如果某台仪器当前处理的原子与上一个处理的原子的电子数之和超过，将产生危险。换句话说，任意两个分配到同一台仪器而且处理顺序相邻的原子的电子数之和必须小于或等于。

现在要将这个序列里的原子按顺序分配到若干台仪器上。注意，分配给各台仪器处理的原子必须按原来序列的相对顺序进行处理。请求出在不产生危险的前提下，最少需要多少台仪器？

输入格式

输入的第1行包含2个整数，依次表示序列的长度和参数。

接下来1行个整数，第个整数表示。

输出格式

输出1行1个整数，表示最少的仪器数。

样例

5 4
1 2 3 1 2

2

解释#1

一种只需要2台仪器的方案如图所示。不可能只用1台仪器完成任务，因为那会导致唯一的一台仪器必须紧接着处理电子数为2和3的两个原子，它们的电子数之和5超过了，会产生危险。

请注意，在分配原子到各台仪器时不能打乱原子的相对次序。

数据范围

• 对于全部数据，有1<=n<=4000，0<=ai<=k<=10^9。
• 测试点1~ 2（共20分）：k=1。
• 测试点3~ 7（共50分）：n <= 300。
• 测试点8~ 10（共30分）：无特殊限制。