Khai Trương Bīngqílín

View as PDF

Submit solution

Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

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

Bedao chuẩn bị khai trương một cửa hàng bán kem! Mọi thứ đã chuẩn bị gần như là đầy đủ: từ địa điểm bán hàng, cho đến menu các loại kem của cửa hàng. Loại kem đặc sắc nhất của Bedao ư? Các bạn hãy xem bài B nhé!

Bây giờ còn một khâu duy nhất trước khi khai trương, đó là treo biển. Biển được treo trước hàng rào của cửa hàng. Hàng rào của cửa hàng tuy thô sơ nhưng mà đơn giản, đời thường, bao gồm ~n~ tấm ván dọc được xếp liên tiếp nhau. Tấm ván thứ ~i~ từ trái sang có độ cao là ~h_i~ dm, và có chiều rộng ~1~ dm.

Biển của cửa hàng Bedao rất rộng, có độ dài đúng bằng ~n~ dm. Để treo biển, Bedao cần chọn ra một chiều cao là ~g~ dm, với ~g~ là số nguyên. Sau đó tại mỗi tấm ván không thấp hơn ~g~ dm, Bedao sẽ đóng một chiếc đinh vào tấm ván này tại vị trí ~g~. Cuối cùng biển sẽ được treo lên tại những chiếc đinh đã đóng.

Bedao được biết rằng, để hàng rào vẫn giữ được tính kiên cố, Bedao không được phép đóng đinh lên quá ~k~ tấm ván. Nhưng Bedao cũng không được cao lắm, do đó Bedao muốn treo biến càng thấp càng tốt.

Cho danh sách độ cao của những tấm ván và số ~k~, hãy giúp Bedao xác định chiều cao ~g~ thấp nhất để treo biển sao cho Bedao không phải đóng đinh quá ~k~ tấm ván, hoặc chỉ ra rằng không tồn tại cách đóng đinh nào thỏa mãn.

Input

Dòng đầu tiên gồm số ~t~ (~1 \le t \le 10\,000~)  – số lượng test case trong input. Tiếp đó là mô tả của ~t~ test case.

Dòng đầu tiên của test case của ~t~ test case chứa hai số nguyên ~n~ và ~k~ (~1 \le k \le n \le 100\,000~)  – số lượng tấm ván trên hàng rào và số lượng tấm ván tối đa được phép đóng đinh lên.

Dòng tiếp theo của test case chứa ~n~ số nguyên ~h_1, h_2, \ldots, h_n~ (~1 \le h_i \le 10^9~)  – chiều cao của các tâm ván theo đơn vị decimet.

Dữ liệu đảm bảo tổng ~n~ của tất cả các test case trong một file input không vượt quá ~10^5~.

Output

Với mỗi test case, hãy in ra độ cao ~g~ (~\displaystyle 1 \le g \le \max_{1 \le i \le n} {a_i}~, ~g~ là số nguyên) thấp nhất để treo biển sao cho Bedao không phải đóng đinh quá ~k~ tấm ván, hoặc in ra ~-1~ nếu như không có cách đóng đinh nào thỏa mãn.

Scoring

  • Subtask 1 (~100~ điểm): ~h_i \le 30~.

  • Subtask 2 (~200~ điểm): không có ràng buộc gì thêm.

Tổng cộng bài toán có ~300~ điểm.

Sample Input

3
3 3
3 2 3
3 2
3 2 3
3 1
3 2 3

Sample Output

1
3
-1

Notes

Trong cả ba ví dụ, các tấm ván có độ cao là ~[3, 2, 3]~.

Trong ví dụ đầu tiên, ~k = 3~, tức Bedao được phép đóng đinh ở tất cả các tấm ván. Ví vậy Bedao có thể chọn độ cao là ~1~.

Trong ví dụ thứ hai, ~k = 2~, tức Bedao chỉ được phép đóng đinh vào tối đa hai tấm ván. Có thể thấy rằng nếu chọn ~g = 1~ hoặc ~g = 2~ thì Bedao đều phải đóng cả ba tấm ván, do đó Bedao nên chọn ~g = 3~.

Trong ví dụ thứ ba, ~k = 1~, tức Bedao chỉ được phép đóng đinh vào tối đa một tấm ván. Dù chọn ~g = 1~, ~g = 2~ hay ~g = 3~ thì Bedao đều phải đóng vào ít nhất là hai tấm ván, do đó không có cách đóng đinh nào thỏa mãn trong trường hợp này.


Comments

Please read the guidelines before commenting.



  • -28
    baolong310876   commented on Jan. 4, 2023, 9:14 a.m. edit 7

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 6
    _Apok__   commented on Jan. 3, 2023, 4:23 p.m. edit 4

    code của mik

    {}


    • 1
      hh123123   commented on Jan. 3, 2023, 4:59 p.m.

      Này ông, tôi không biết mọi người thấy meme này như thế nào, nhưng đối với tôi, nó tuyệt lắm, cơ mà có vẻ như nó không đáp ứng được tiêu chí là một món ăn tinh thần cho anh em trong group và cả tôi, tôi chắc chắn rằng ông có thể tạo ra những meme còn tuyệt hơn như thế này nhiều, tôi và cả anh em trong group cảm thấy thật hạnh phúc khi có ông trong group, chúng tôi tự hào và xúc động về những cố gắng ông đã đóng góp để phát triển group của chúng ta, tôi thật may mắn vì đã gặp được ông, chào ông và thân ái


      • -3
        HDANTN   commented on Jan. 4, 2023, 9:38 a.m.

        ??