A: 烘干

1001: 烘干

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 29  Accepted: 1
[Submit][Status][Web Board]

Description

现在,有一堆刚洗完的衣服,每件衣服有一定的含水量,我现在想把这些衣服晾干。
每件衣服每分钟会自动蒸发掉1滴水,于是我想利用烘干机帮助我弄干这些衣服。
烘干机每分钟可以烘干一件衣服上的最多k滴水,用烘干机的时候水不会蒸发
你在使用烘干机烘干某件衣服的时候,其他衣服仍然可以每分钟自动蒸发一滴水。
现在我需要你帮助我算出我弄干所有衣服的最短时间。

Input

多组测试数据,每组数据第一行输入一个n代表衣服的件数。
接下来一行输入n个数,a1,a2..an,每个数表示每件衣服的含水量(单位:滴)。
下面一行输入k,表示烘干机每分钟可以烘干一件衣服上的k滴水。
数据范围:1≤n≤100000,1≤ai≤1e9,1≤k≤1e9。

Output

弄干所有衣服的最少时间。

Sample Input

3
2 3 9
5
3
2 3 6
5

Sample Output

3
2

HINT

 对于样例1:


前两件衣服可以在3分钟以内晾干,同时最后一件衣服可以烘干机2分钟烘干,所以烘干所有衣服的最短时间是3分钟。

[Submit][Status][Web Board]