在一个繁忙的城市中，有多家银行同时开展客户奖励活动。每家银行将根据客户的存款数量颁发一定数量的。
具体而言，对于每 k 个客户开户，银行将颁发一枚金币。也就是说，如果某家银行有t 个客户，该银行将颁发 \left\lfloor \frac{t}{k} \right\rfloor 枚金币，其中 \left\lfloor x \right\rfloor 表示不超过 x 的最大整数。目前，第 i 家银行有 a_i 个客户。
小张是一名银行经理，他的目标是为 m 位新客户分配到各家银行，以使所有银行颁发的金币总数最大化。请帮助他合理分配这些新客户的存款。
有多组测试数据。第一行输入一个整数 T (1 \leq T \leq 10) 表示测试数据组数，对于每组测试数据：
- 第一行输入两个整数 n 和 k (1 \leq n \leq 100, 1 \leq k \leq 10^9)
- 第二行输入 n 个整数 a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9)，其中 a_i 表示第 i 家银行当前的客户人数。
- 第三行输入一个整数 m (1 \leq m \leq 10^9)，表示小张需要为多少位新客户安排存款。
每组数据输出一行一个整数，表示所有银行最多一共颁发多少枚金币。
2 3 10 239 141 526 6 2 1 300 100 1000
91 1400
10 5 69 737496964 118666832 224453745 812072933 417933419 921166325 5 69 917989159 389024325 153046283 771563567 850976709 32654091 5 69 414694579 340395263 61984364 269418497 349581026 743178272 5 69 612156300 778350600 25021622 627932959 784925732 910642497 5 69 696153489 610050032 705097897 582820635 864065403 909330427 5 69 543383748 374215700 531080319 789315695 703175194 47104600 5 69 991201923 645981994 991150159 846684194 655467103 51127255 5 69 832323904 348582367 401678092 638645504 2158328 380372442 5 69 915563370 54395014 120278580 554348366 515834491 837704691 5 69 494597840 371982519 766354044 947603037 785162903 793152210
46837539 45148610 31583362 54188836 63297360 43308337 60603081 37735661 43451079 60273225
解释
将 2 位新客户分配到第 1 家银行，4 位新客户分配到第 3 家银行。金币总数计算如下：
- 第 1 家银行： \left\lfloor \frac{23 + 2}{10} \right\rfloor = \left\lfloor \frac{25}{10} \right\rfloor = 2
- 第 3 家银行： \left\lfloor \frac{14 + 0}{10} \right\rfloor = \left\lfloor \frac{14}{10} \right\rfloor = 1
- 第 2 家银行： \left\lfloor \frac{52 + 4}{10} \right\rfloor = \left\lfloor \frac{56}{10} \right\rfloor = 5
因此，金币总数为：2 + 1 + 5 = 8
数据范围与约定
- 对于 20\% 的数据范围，满足 n \leq 10
- 对于 50\% 的数据范围，满足 n \leq 100
- 对于 100\% 的数据，满足：1 \leq n \leq 2 \times 10^5, 1 \leq k,m,a_i \leq 10^9, 1 \leq T \leq 10
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |