问题 1303. -- jlz的刷题黑科技

1303: jlz的刷题黑科技

时间限制: 1 Sec  内存限制: 128 MB
提交: 191  解决: 61
[提交][状态][讨论版]

题目描述

众所周知,jlz特别喜欢刷题。并且,jlz与普通人刷题不一样,他可以同时刷很多道题!
对于很多道题,jlz每分钟可以完成所有未完成的题的一分钟的工作量。
但是最近,jlz又学会了一项刷题的黑科技,他每分钟还可以额外完成某一道题的k分钟的工作量。
现在jlz遇到了n道题,已知每道题他完成所需的时间,请你帮他算算,通过合理使用黑科技jlz完成所有题目所需的最短时间。

输入

第一行输入测试组数T。对于每组数据,第一行输入n,1<=n<=100000,紧接着输入一行,
n个整数,第i个数字代表a1,a2,…,an,第三行输入一个数字k,其中1<=T<=10,1<=ai<=1000000000,1<=i<=n,1<=k<=1000000000.

输出

每组数据输出一行结果,该行仅包含一个整数,表示该组数据jlz切题花费的最少时间

样例输入

2
3 
2 3 9 
5
3 
2 3 7
5

样例输出

3
2

提示

对于第一组数据,jlz可以分别在第一分钟与第二分钟对第三道题使用各使用一次黑科技,使得在3分钟内切掉所有题目。

对于第二组数据,jlz可以分别在第一分钟对第二道题使用一次黑科技,第二分钟对第三道题使用使用一次黑科技,使得在2分钟内切掉所有题目。

来源

[提交][状态][讨论版]