綾正在商場中閒逛，一台扭蛋機吸引了她的目光。 扭蛋機中共有 $n$ 種扭蛋，第 $i$ 種扭蛋有 $a_i$ 個。

• 消耗一個扭蛋幣可隨機獲得一個扭蛋。
• 消耗任意 $k$ 個扭蛋可以向商家兌換一個指定幣。
• 消耗一個指定幣可獲得扭蛋機中一個指定種類的扭蛋。

所有扭蛋不會被重新放回扭蛋機。 綾想要集齊 $n$ 種扭蛋，即在最後擁有每種扭蛋各至少一個，現在她想要知道，至少需要多少扭蛋幣才能保證可以集齊 $n$ 種扭蛋。

輸入格式

本題有多組數據。第一行一個正整數 $T$ ($1 \le T \le 3000$)，表示數據組數。

對於每組數據： 第一行兩個正整數 $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^5$)，分別表示扭蛋種類數和兌換指定幣所需要的扭蛋數量。 第二行 $n$ 個正整數，第 $i$ 個正整數為 $a_i$ ($1 \le a_i \le 3000$)，表示第 $i$ 種扭蛋的數量。

保證 $T$ 組數據中 $n$ 的和不超過 $3000$。

輸出格式

對於每組數據： 輸出一行一個整數，表示保證集齊 $n$ 種扭蛋至少需要的扭蛋幣數量。

範例

範例輸入 1

2
2 2
1 4
4 3
8 7 6 5

範例輸出 1

3
9