Responsive image

问题 3383 --金奖

3383: 金奖

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 12
[提交][状态][讨论版][命题人:]

题目描述

真是忙碌的一周！本周末有n场编程竞赛将同时举行。
每场比赛将为每k支参赛队伍颁发一枚金牌。也就是说，如果有t支队伍参赛，则将颁发t/k(向下取整)枚金牌，目前，有ai支队伍参加第i场竞赛。
包包是一所大学的教练，他有m支队伍，他还没有决定这些队伍应该参加哪些比赛。请你帮他给每支队伍分配一个比赛项目，使所有比赛的金牌总数达到最大。

输入描述

有多个测试用例。输入的第一行包含一个整数 T ( 1<T<100 )，表示测试用例的数量。对于每个测试用例
第一行包含两个整数n和k( 1<n<100, 1<k<109 )，表示比赛次数和金牌比例。
第二行包含 n个整数 ai, 其中 ai是当前参加i场比赛的队伍数量。
第三行包含一个整数m( 1<m<109)，表示需要分配给比赛的队伍数量。

输出描述

对每个测试用例输出一行，其中包含一个整数，表示所有比赛发放的金牌总数上限。

样例输入

2
3 10
239 141 526
6
2 1
300 100
1000

样例输出

91
1400

提示

对于第一个样本测试案例，请派出 2支队伍参加第1场竞赛，并派出4支队伍参加第3场竞赛。金牌总数为(239+2)/10 + (141+0)/10 + (526+4)/10 =24+14+53=91。

来源

23软4杨宗奇 

[提交][状态]
ACM算法攻关部