Lăng đang đi dạo trong trung tâm thương mại thì bị thu hút bởi một chiếc máy gacha. Trong máy gacha có tổng cộng $n$ loại trứng, loại thứ $i$ có $a_i$ quả.

• Tiêu tốn một đồng xu gacha để nhận ngẫu nhiên một quả trứng.
• Tiêu tốn bất kỳ $k$ quả trứng nào để đổi lấy một đồng xu chỉ định từ người bán.
• Tiêu tốn một đồng xu chỉ định để nhận một quả trứng thuộc loại chỉ định từ máy gacha.

Tất cả trứng sau khi lấy ra sẽ không được bỏ lại vào máy. Lăng muốn thu thập đủ $n$ loại trứng, nghĩa là cuối cùng cô ấy phải có ít nhất một quả của mỗi loại. Bây giờ cô ấy muốn biết, cần ít nhất bao nhiêu đồng xu gacha để đảm bảo có thể thu thập đủ $n$ loại trứng.

Dữ liệu vào

Bài toán có nhiều bộ dữ liệu. Dòng đầu tiên chứa một số nguyên dương $T$ ($1 \le T \le 3000$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu:

Dòng đầu tiên chứa hai số nguyên dương $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^5$), lần lượt biểu thị số loại trứng và số lượng trứng cần thiết để đổi lấy một đồng xu chỉ định.

Dòng thứ hai chứa $n$ số nguyên dương, số nguyên thứ $i$ là $a_i$ ($1 \le a_i \le 3000$), biểu thị số lượng của loại trứng thứ $i$.

Đảm bảo tổng $n$ trong $T$ bộ dữ liệu không vượt quá $3000$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu:

In ra một dòng chứa một số nguyên, biểu thị số lượng đồng xu gacha tối thiểu cần thiết để đảm bảo thu thập đủ $n$ loại trứng.

Ví dụ

Dữ liệu vào 1

2
2 2
1 4
4 3
8 7 6 5

Dữ liệu ra 1

3
9