问题 D: 新春---来吃糖

问题 D: 新春---来吃糖

时间限制: 1 Sec  内存限制: 256 MB
提交: 48  解决: 16
[提交][状态][讨论版][命题人:]

题目描述

幼儿园有N个小朋友,有男孩也有女孩,他们按照水平方向拍成一行,每个小朋友所占的位置编号分别是1,2,....,N。

你是幼儿园的老师,幼儿园有两种糖果,分别是男孩喜欢的糖果和女孩喜欢的糖果。现在有一定数量的篮子,每个篮子只能装一种糖果,装糖果的数量可以是无限的。由于小朋友比较小,至多愿意移动k个位置到装有自己喜欢的糖果的篮子里去取糖。现在需要你选择1,2,.....,N的位置放置糖果篮,每个位置只能放一个糖果篮。由于篮子的数量有限,现在请你计算出最少需要多少个篮子能保证每个小朋友都能取到自己喜欢的糖果。

输入

第一行两个整数N,K,分别表示小朋友的数量以及移动的最大位置。

第二行n个整数ai,用空格分隔,每个整数都是0或1。0表示第第i个位置是男孩,1表示第i个位置是女孩。

输出

一个整数,表示需要的最少篮子的数量

样例输入

5 0
0 1 1 0 0

样例输出

5

提示


1<=N<=2*10^5



0<=K<=N-1

[提交][状态]