当前没有测试数据。

题目描述

有一个专门粉碎土豆的处理器。你可以把它想象成一个圆柱体，土豆从上面塞入，从下面粉碎后吐出。每个土豆可以视为条状，与处理器等宽。

处理器中可以放入多个土豆，但这些土豆的总高度不能超过 $h$ 厘米（否则会盖不上盖子，启动不了机器）。处理器每秒最多会粉碎 $k$ 厘米的土豆。

小A有 $n$ 块土豆，第 $i$ 块的长度为 $a_i$ 厘米。他需要把这些土豆按顺序从 $1$ 号到 $n$ 号放进处理器。

求粉碎完所有土豆的最短用时。

格式

输入格式：

第一行：三个整数 $n$、$h$ 和 $k$ ，含义与题目中相同。

第二行：$n$ 个整数，分别表示每块土豆的长度（单位：厘米）。

输出格式：

一个整数，表示粉碎完所有土豆的最短用时（单位：秒）。

样例 #1

样例输入 #1

5 6 3
5 4 3 2 1

样例输出 #1

5

样例 #2

样例输入 #2

5 6 3
5 5 5 5 5

样例输出 #2

10

样例 #3

样例输入 #3

5 6 3
1 2 1 1 1

样例输出 #3

2

数据范围与约束

对于20%的数据，$a_i$ 是 $k$ 的倍数；

对于50%的数据，$1≤n≤100,1≤k,a_i≤h≤10^6$；

对于100%的数据，$1≤n≤10^5,1≤k,a_i≤h≤10^9$。