轮班清扫

任务排好了，但矿区还有一片废墟没清理——塌方的通道，碎裂的管道，散落的零件。

"要清扫。"CC说，"找人轮班，把路清出来。"

"多少人？"

"不多。"CC说，"就我们几个，加几个还能动的矿工。"

"那咋排班？"

"覆盖。"你说，"每个时段都要有人清扫。但人不能连轴转——最多连续工作$m$小时，然后必须休息$n$小时。"

"这是DS优化？"

"对。"你说，"用数据结构优化DP。设$dp[i]$为覆盖到第$i$个小时的最少人数。"

"转移？"

"从前面某个时段$j$转移。"你说，"$dp[i]=\min(dp[j]+1)$，其中从$j+1$到$i$可以由一个人连续覆盖。"

"但连续工作不能超过$m$小时。"

"对。"你说，"所以$i-j\le m$。"

"而且休息要$n$小时——下一个人必须在$j-n$之前开始？"

"不。"你说，"同一个人不能连续两段。但可以是不同的人。"

"那就是——只要$j$之前有人覆盖，就可以加一个人覆盖$j+1$到$i$。"

"对。"

你开始写。用线段树维护区间最小值，快速查询$dp[j]$。

"第1小时到第4小时。"你说，"一个人覆盖。$dp[4]=dp[0]+1=1$。"

"第5小时到第8小时。"你说，"另一个人覆盖。$dp[8]=dp[4]+1=2$。"

"第9小时到第12小时。"你说，"$dp[12]=dp[8]+1=3$。"

"12小时，3个人轮班。"

"对。"你说，"每人干4小时，休息8小时。"

"如果只有2个人？"

"那就覆盖不了12小时。"你说，"2个人最多覆盖8小时（每人干4小时，不能重叠）。"

"人不够。"

"对。"你说，"所以我们要加快——每人干6小时，覆盖12小时，但会累。"

"累也得干。"

"对。"CC说，"累也得干。"

她把铁锹扛在肩上——那把从矿场带出来的铁锹，柄已经磨光了。

"我先干。"她说，"你们休息。"

"你刚爬过来。"

"我休息够了。"她说，"在碎石堆里，我睡了三天。"

"那不是睡。"

"那就是睡。"她说，"闭上眼，啥都不想。就是睡。"

题目描述

给定$m$小时的清扫任务。每个人可以连续工作最多$k$小时，然后必须休息。求覆盖全部$m$小时所需的最少人数。

输入格式

$m,k$。

输出格式

最少人数。如果无法覆盖，输出-1。

输入样例

5
1 2 3 4 5

输出样例

-1

提示

• DS优化DP（线段树/树状数组）。
• $dp[i]$为覆盖到第$i$小时的最少人数。
• $dp[i]=\min_{j<i,k\ge i-j}(dp[j]+1)$。
• 用线段树维护区间最小值，快速查询。