题目描述

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

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

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

每秒会发生如下事件：

1. 如果还有至少一条土豆没放进去，瓦尼亚将它们逐一放入处理器，直到没有足够的空间放置下一片，即塞到塞不进为止。
2. 处理器粉碎了 $k$ 厘米或剩下全部的土豆。

输入格式

输入的第一行包含整数 $n$、$h$ 和 $k$（$1≤n≤10^5,1≤k≤h≤10^9$），含义如上。

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

输出格式

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

5 6 3
5 4 3 2 1

5

5 6 3
5 5 5 5 5

10

5 6 3
1 2 1 1 1

2