Mã bài:
cutline
Điểm:
2 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
64M
Dữ liệu vào:
stdin
Dữ liệu ra:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Golang, Java, Pascal, Perl, Python, Rust
Có ~N~ sợi dây, sợi thứ ~i (i = 1...N)~ có độ dài ~L_i~ là một số nguyên dương. Để tạo ra ~K~ đoạn dây mà mỗi đoạn dây có độ dài đúng bằng ~M~, người ta chọn và cắt một số sợi dây trong ~N~ sợi dây đã cho tại các vị trí nguyên. Biết rằng mỗi nhát chỉ cắt được một sợi dây thành hai đoạn.
Yêu cầu: Tính số nhát cắt ít nhất để có được đúng ~K~ đoạn dây mà mỗi đoạn có độ dài đúng bằng ~M~.
##Dữ liệu vào
• Dòng đầu tiên ghi ba số nguyên dương ~N, K~ và ~M~ ~(N, M ≤ 10^5; K ≤ 10^9)~;
• Dòng thứ hai ghi ~N~ số nguyên dương ~L_1, L_2, ..., L_N~ có giá trị không vượt quá ~10^6~.
Các số trên cùng một dòng được ghi cách nhau bởi một dấu cách.
Dữ liệu ra
• Một số duy nhất là số nhát cắt ít nhất tìm được. Nếu bài toán không có lời giải thì ghi số ~-1~.
Sample Input
6 11 3
1 2 9 15 7 11
Sample Output
9
Bình luận