Giải bài trực tuyến

Bà của Ellenora thường ra cho cháu gái mình những bài toán đố mà Elly coi là bí hiểm. Buổi tối vừa rồi bà đố Elly bài toán sau:

“Ở cửa hàng cạnh nhà ta có k mặt hàng với giá khác nhau từ 1 đến k. Bà có n đồng tiền mệnh giá a₁, a₂, . . ., a_n. Bà định sang bên đấy mua một mặt hàng nào đó, trả đúng giá của nó mà không phải nhận lại tiền thừa. Nhưng bà đã già quá rồi. Bà không muốn mang tất cả tiền của mình đi, có thể lẫn hoặc rơi mất, vì vậy bà chỉ mang theo một số đồng đầu tiên. Vậy bà phải mang theo ít nhất bao nhiêu đồng tiền để mua được mặt hàng bất kỳ?”

Chỉ mất vài giây Elly đã đưa ra được câu trả lời và nghĩ thầm trong bụng: “Ôi, bà ơi, lại những bài toán giải thuật quá chuẩn!”.

Bạn có thể đua tài với Elly bằng cách viết chương trình giải bài toán này được không?

Dữ liệu: Vào từ file văn bản RIDDLE.INP:

• Dòng đầu tiên chứa số nguyên T – số lượng tests trong file,
• Mỗi test cho trên 2 dòng:
  • Dòng thứ nhất chứa 2 số nguyên n và k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁶),
  • Dòng thứ 2 chứa n số nguyên a₁, a₂, . . ., a_n , (0 < ai ≤ 10⁵, "i = 1 ÷ n).

Kết quả: Đưa ra file văn bản RIDDLE.OUT, kết quả mối test đưa ra trên một dòng dưới dạng số nguyên. Nếu không có cách mang thì đưa ra số -1.

Ví dụ: