题目描述

瓦尼亚在一个垂直的食品处理器中粉碎土豆。 你可以把它想象成一个圆柱体，从上面塞入，从下面粉碎后吐出。 每个土豆可以视为条状。

处理器中的土豆高度不超过$h$(否则会满出来)，处理器每秒粉碎$k$厘米的土豆。如果处理器里剩不到$k$厘米土豆，则粉碎所有剩余的土豆。

瓦尼亚有$n$条土豆，第$i$块的长度等于$a_i$。他把它们按顺序从$1$号到$n$号放进食品处理器，从$1$号开始，到$n$号结束。

每秒会发生如下事件：

1.如果还有至少一条土豆没放进去，瓦尼亚将它们逐一放入处理器，直到没有足够的空间放置下一片，即塞到塞不进为止。

2.处理器粉碎了$k$厘米或剩下全部的土豆。

输入输出格式

输入格式：

输入的第一行包含整数$n$、$h$和$k$ （$1≤n≤100 000,1≤k≤h≤109$），含义如上。

第二行包含$n$个整数$a_i$（1≤a_i≤h），即土豆长度。

输出格式：

最短需要粉碎所有土豆的时间。

样例 #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