扭蛋

题目描述

绫正在商场中闲逛，一台扭蛋机吸引了她的目光。扭蛋机中共有$n$种扭蛋，第i种扭蛋有$a_i$个。

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

所有扭蛋不会被重新放回扭蛋机。绫想要集齐$n$种扭蛋（即最后拥有每种扭蛋各至少一个），现在她想要知道，至少需要多少扭蛋币才能保证可以集齐$n$种扭蛋。

输入格式

本题有多组数据。

• 第一行一个正整数$T（1≤T≤3000）$，表示数据组数。
• 对于每组数据：
  • 第一行两个正整数$n、k（1≤n≤3000，1≤k≤3×10⁵）$，分别表示扭蛋种类数和兑换指定币所需要的扭蛋数量。
  • 第二行$n$个正整数，第$i$个正整数为$a_i（1≤ai≤3000）$，表示第$i$种扭蛋的数量。

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

输出格式

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

2
2 2
1 4
4 3
8 7 6 5

3
9