Bí hiểm

View as PDF

Submit solution


Points: 0.32 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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_{1}, a_{2}, \dots, 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?

Input

  • 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 \leq n \leq 10^{5}~, ~1 \leq k \leq 10^{6})~,
    • Dòng thứ ~2~ chứa ~n~ số nguyên ~a_{1}~, ~a_{2}~, ..., ~a_{n}~, ~(0 < a_i \leq 10^{5}~, " ~i = 1, 2, \dots, n)~.

Output

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~.

Sample Input

3
7 10
1 2 3 4 5 6 7
3 3
2 4 1
3 6
3 1 4

Sample Output

4
3
-1

Comments

Please read the guidelines before commenting.


There are no comments at the moment.