问题 B: 土豆

内存限制:256 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:279 通过:101

题目描述

瓦尼亚在一个垂直的食品处理器中粉碎土豆。
你可以把它想象成一个圆柱体,从上面塞入,从下面粉碎后吐出。
每个土豆可以视为条状。
处理器中的土豆高度不超过ℎ(否则会满出来),处理器每秒粉碎k厘米的土豆。如果处理器里剩不到k厘米土豆,则粉碎所有剩余的土豆。
瓦尼亚有n条土豆,第i 块的长度等于ai。他把它们按顺序从1号到n号放进食品处理器,从1号开始,到n号结束。
每秒会发生如下事件:
1.如果还有至少一条土豆没放进去,瓦尼亚将它们逐一放入处理器,直到没有足够的空间放置下一片,即塞到塞不进为止。
2.处理器粉碎了k 厘米或剩下全部的土豆。

输入格式

输入的第一行包含整数 n、h 和 k (1≤n≤100000,1≤k≤h≤10^9)− 马铃薯块数、食品加工机的高度和每秒粉碎的马铃薯量。
第二行包含 n 个整数 ai (1≤ai≤h)− 马铃薯块的高度。

输出格式

打印单个整数 ——-即按照问题陈述中描述的过程粉碎所有土豆所需的秒数。
Examples
Input
5 6 3
5 4 3 2 1
Output
5
Input
5 6 3
5 5 5 5 5
Output
10
Input
5 6 3
1 2 1 1 1
Output
2


输入样例 复制

5 6 3
5 4 3 2 1

输出样例 复制

5

数据范围与提示

考虑第一个示例。
首先万尼亚将高度为5的土豆放入处理器中。在第一秒结束时,里面只剩下高度 2 的数量。
现在万尼亚把那块高度为 4 的土豆。在第二秒结束时,还剩下高度 3。
万尼亚把那块高度为3的那块放进去,在第三秒结束时,又只剩下3厘米了。
万尼亚终于把高度2和1的碎片放了进去。在第四秒结束时,处理器中马铃薯的高度等于 3。
在下一个加工过程即第五秒中,最终粉碎了所有剩余的马铃薯,该过程完成。
在第二个样本中,Vanya 将高度为 5 的那块放入里面,等待 2 秒钟,然后它被完全粉碎。然后他对其他 4 件作品重复相同的过程。总时间等于 2·5=10 秒。
在第三个样本中,Vanya 只需将所有马铃薯放入处理器并等待 2 秒钟。