Vanya 在立式食品加工机中捣碎土豆。在每个时刻,处理机中马铃薯的高度不超过 h,并且处理机每秒粉碎 k 厘米的马铃薯。如果剩余的马铃薯少于 k 厘米,则在第二个处理器中会粉碎所有剩余的马铃薯。
Vanya 有 n 块土豆,第 i 块的高度等于 ai。他将它们从 1 号物品开始,一直到 n 号物品,一件一件地放入食品加工机中。正式来说,每一秒都会发生以下情况:
1. 如果至少还剩下一块土豆,Vanya 会将它们一块一块地放入处理器中,直到没有足够的空间容纳下一块。
2. 处理器粉碎 k 厘米的土豆(或里面的所有东西)。
提供食品加工机的参数和连续每个土豆的大小信息,计算需要多长时间才能将所有土豆打碎。
输入
输入的第一行包含整数 n、h 和 k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ h ≤ 109)——分别是土豆片的数量、食品加工机的高度和每秒粉碎的土豆量。
第二行包含 n 个整数 ai (1 ≤ ai ≤ h) — 棋子的高度。
输出
打印一个整数——按照问题陈述中描述的过程粉碎所有土豆所需的秒数。
示例
输入 #1
5 6 3 5 4 3 2 1
输出 #1
5
输入 #2
5 6 3 5 5 5 5 5
输出 #2
10
输入 #3
5 6 3 1 2 1 1 1
输出 #3
2
注意
考虑第一个样本。
1. 首先 Vanya 将高度为 5 的马铃薯块放入加工机中。在第二个结束时,内部只剩下高度 2。
2. 现在,Vanya 放入了高度为 4 的土豆块。第二次结束时,剩余高度为 3 的土豆。
3. Vanya 将高度为 3 的棋子放入内部,在这一秒结束时再次只剩下 3 厘米。
4. Vanya 最后将高度为 2 和 1 的棋子放入其中。第二步结束时,处理机中马铃薯的高度等于 3。
5. 在第二个处理器中,最终粉碎了所有剩余的马铃薯,并且该过程完成。
在第二个样本中,Vanya 将高度为 5 的碎片放入其中并等待 2 秒,直至其完全粉碎。然后他对另外 4 件作品重复相同的过程。总时间等于2·5 = 10 秒。
在第三个示例中,Vanya 只是将所有土豆放入处理器中并等待 2 秒。