You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小A正在玩一款打怪兽的游戏。

已知共有n只怪兽，每只怪兽的血量为a[i]。

小A可以使用两种武器攻击怪兽。

第一种武器是手枪，每打中一枪，只能使怪兽的血量值减少1。 手枪的子弹是不受限制的，也就是它有无限发子弹。

第二种是火箭炮，每打中一炮，可以将怪兽的血量值减少X。 可惜，火箭炮的炮弹是有数量限制的，目前，小A只有K发火箭炮的炮弹。

小A想知道，在他打出的每一发子弹和炮弹都能命中怪兽的情况下， 他至少用要用手枪打多少枪，才可以消灭所有的怪兽。

输入

共两行。

第一行三个正整数n, X, K，依次表示怪兽的数量； 使用火箭炮命中一炮，对怪兽的伤害值；小A拥有的火箭炮的炮弹数量。

第二行，n个正整数，第i个数为a[i]，表示第i只怪兽的血量值。

输入数据中，同一行内，相邻两个数之前用一个空格隔开。

输出

输出一个整数，表示小A需要使用手枪的最少攻击次数。

样例

5 4 3
1 2 3 4 5 

4

数据范围

100%的数据：1<=n=1e6，1<=X<=1000，1<=a[i]<=1e9, 1<=K<=1e18