Bessie đã theo học chương trình tiến sĩ khoa học máy tính vì yêu thích ngành này, đồng thời bị cuốn hút bởi viễn cảnh một ngày nào đó trở thành “Tiến sĩ Bessie”. Sau một thời gian nghiên cứu, cô đã công bố \(N\) bài báo (\(1\le N\le10^5\)); bài báo thứ \(i\) nhận được \(c_i\) lượt trích dẫn (\(0\le c_i\le10^5\)) từ các bài báo khác trong giới nghiên cứu.

Bessie nghe nói thành công của một nhà khoa học có thể được đo bằng chỉ số \(h\). Chỉ số \(h\) là số nguyên lớn nhất \(h\) sao cho nhà khoa học có ít nhất \(h\) bài báo, mỗi bài có ít nhất \(h\) lượt trích dẫn. Ví dụ, một người có \(4\) bài báo với số lượt trích dẫn tương ứng là \((1,100,2,3)\) có chỉ số \(h\) bằng \(2\); nếu các số lượt trích dẫn là \((1,100,3,3)\) thì chỉ số \(h\) bằng \(3\).

Để tăng chỉ số \(h\), Bessie dự định viết tối đa \(K\) bài tổng quan (\(0\le K\le10^5\)), mỗi bài trích dẫn nhiều bài báo trước đây của cô. Tuy nhiên, do giới hạn số trang, mỗi bài tổng quan chỉ có thể trích dẫn tối đa \(L\) bài báo (\(0\le L\le10^5\)). Một bài báo không thể được trích dẫn nhiều lần trong cùng một bài tổng quan, nhưng có thể được trích dẫn trong nhiều bài tổng quan.

Hãy xác định chỉ số \(h\) lớn nhất mà Bessie có thể đạt được sau khi viết các bài tổng quan này. Bessie không được trích dẫn một bài tổng quan từ một bài tổng quan khác của chính mình.

Lưu ý rằng cố vấn của Bessie có lẽ nên nói cho cô biết việc viết bài tổng quan chỉ nhằm tăng chỉ số \(h\) là không đúng đắn về mặt đạo đức; các nhà khoa học khác không nên noi theo Bessie.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(K\) và \(L\).

Dòng thứ hai chứa \(N\) số nguyên \(c_1,\ldots,c_N\) cách nhau bởi dấu cách.

Dữ liệu ra

In chỉ số \(h\) lớn nhất trên một dòng.

Phân nhóm

• Các test 1-6 thỏa mãn \(N\le100\).
• Các test 7-16 không có ràng buộc bổ sung.

Ví dụ

4 4 1
1 100 1 1

3

4 1 4
1 100 1 1

2

Giải thích ví dụ 1. Bessie có thể viết tối đa \(4\) bài tổng quan, mỗi bài trích dẫn tối đa \(1\) bài báo. Nếu cô trích dẫn mỗi bài trong số bài báo thứ nhất và thứ ba hai lần, chỉ số \(h\) của cô trở thành \(3\).

Giải thích ví dụ 2. Bessie có thể viết nhiều nhất một bài tổng quan. Nếu cô trích dẫn bất kỳ bài nào trong số bài báo thứ nhất, thứ ba hoặc thứ tư ít nhất một lần, chỉ số \(h\) của cô trở thành \(2\).

Nguồn

USACO 2021 US Open, Silver - Acowdemia: https://usaco.org/index.php?page=viewproblem2&cpid=1136

Tác giả: Dhruv Rohatgi.