在一个繁忙的城市中，有多家银行同时开展客户奖励活动。每家银行将根据客户的存款数量颁发一定数量的。具体而言，对于每k元存款，银行将颁发一枚金币。也就是说，如果客户在某家银行存款了t元，该银行将颁发 
枚金币，其中
表示不超过x的最大整数。目前，第i家银行有ai元的客户存款。
小张是一名银行经理，他的目标是为新客户的总共m元的存款分配存款到各家银行，以使所有银行颁发的金币总数最大化。请帮助他合理分配这些新客户的存款。
在一个繁忙的城市中，有多家银行同时开展客户奖励活动。每家银行将根据客户的存款数量颁发一定数量的。具体而言，对于每k元存款，银行将颁发一枚金币。也就是说，如果客户在某家银行存款了t元，该银行将颁发 枚金币，其中表示不超过x的最大整数。目前，第i家银行有ai元的客户存款。
小张是一名银行经理，他的目标是为新客户的总共m元的存款分配存款到各家银行，以使所有银行颁发的金币总数最大化。请帮助他合理分配这些新客户的存款。
有多组测试数据。第一行输入一个整数T(1<=T<=10) 表示测试数据组数，对于每组测试数据：
样例1
2
3 10
239 141 526
6
2 1
300 100
1000
样例2
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样例1
91
1400
样例2
46837539
45148610
31583362
54188836
63297360
43308337
60603081
37735661
43451079
60273225
对于20%的数据范围，满足n<=10
对于50%的数据范围，满足n<=100
对于100%的数据，满足：1<=n<=2*10^5 1<=k,m,ai<=10^9 1<=T<=10