题目描述

绫正在商场中闲逛，一台扭蛋机吸引了她的目光。

扭蛋机中共有 n 种扭蛋，第 i 种扭蛋有 ai​ 个。

• 消耗一个扭蛋币可随机获得一个扭蛋。
• 消耗任意 k 个扭蛋可以向商家兑换一个指定币。
• 消耗一个指定币可获得扭蛋机中一个指定种类的扭蛋。

所有扭蛋不会被重新放回扭蛋机。

绫想要集齐 n 种扭蛋，即在最后拥有每种扭蛋各至少一个，现在她想要知道，至少需要多少扭蛋币才能保证可以集齐 n 种扭蛋。

输入格式

本题有多组数据。第一行一个正整数 T (1≤T≤3000)，表示数据组数。

对于每组数据：

第一行两个正整数 n,k ($1≤n≤3000,1≤k≤3×10^5$)，分别表示扭蛋种类数和兑换指定币所需要的扭蛋数量。

第二行 n 个正整数，第 i 个正整数为 ai​ ($1≤ai​≤3000$)，表示第 i 种扭蛋的数量。

保证 T 组数据中 n 的和不超过 3000。

输出格式

对于每组数据：

输出一行一个整数，表示保证集齐 n 种扭蛋至少需要的扭蛋币数量。

输入输出样例 #1

输入 #1

2
2 2
1 4
4 3
8 7 6 5

输出 #1

3
9