Ổ chia điện

Điểm: 2,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Vasya có nhiều thiết bị điện. Trong nhà, anh có $k$ ổ cắm trên tường và $n$ ổ chia điện (mỗi ổ chia điện thứ $i$ có $a_{i}$ ổ cắm). Mỗi thiết bị hoặc ổ chia điện đều cần chiếm đúng một ổ cắm để hoạt động — ổ cắm đó có thể là ổ cắm trên tường hoặc một ổ cắm trên một ổ chia điện khác đã được cắm điện.

Một thiết bị (hoặc ổ chia điện) được coi là "đã có điện" nếu nó được cắm trực tiếp vào một trong $k$ ổ cắm trên tường, hoặc được cắm vào một ổ chia điện khác mà ổ chia điện đó đã có điện.

Vasya có $m$ thiết bị cần được cấp điện đồng thời. Hãy tìm số ổ chia điện tối thiểu trong $n$ ổ chia điện mà Vasya cần dùng để cấp điện cho tất cả $m$ thiết bị. Nếu dùng cả $n$ ổ chia điện vẫn không đủ thì in ra $- 1$ .

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$ , $m$ , $k$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — số ổ cắm trên mỗi ổ chia điện.

Dữ liệu ra

In ra một số nguyên — số ổ chia điện tối thiểu cần dùng, hoặc $- 1$ nếu không thể.

Ràng buộc

$1 \leq n, m, k \leq 50$
$1 \leq a_{i} \leq 50$

Ví dụ

Input	Output	Giải thích
3 5 3 3 1 2	1	Cắm ổ chia điện thứ nhất (3 ổ cắm) trực tiếp vào tường. Sau khi cắm, còn $2$ ổ cắm tường trống + $3$ ổ cắm trên ổ chia = $5$ ổ cắm, đủ cho $5$ thiết bị.
4 7 2 3 3 2 4	2	Cắm ổ chia điện thứ tư (4 ổ) trực tiếp vào tường, rồi cắm ổ chia điện thứ nhất (3 ổ) vào một trong các ổ của ổ chia thứ tư. Tổng số ổ trống = $1 + 3 + 3 = 7$ .
5 5 1 1 3 1 2 1	-1	Dù dùng hết tất cả ổ chia, tổng số ổ trống chỉ đạt $1 + (1 - 1) + (3 - 1) + (1 - 1) + (2 - 1) + (1 - 1) = 4 < 5$ .

Bình luận

Không có bình luận tại thời điểm này.