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 một bài tổng quan có trích dẫn một số bài báo trước đây của mình. Do giới hạn số trang, cô chỉ có thể đưa vào tối đa \(L\) lượt trích dẫn (\(0\le L\le10^5\)), và tất nhiên mỗi bài báo của cô chỉ có thể được trích dẫn nhiều nhất một lần.

Hãy xác định chỉ số \(h\) lớn nhất mà Bessie có thể đạt được sau khi viết bài tổng quan này.

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\) 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 mà Bessie có thể đạt được sau khi viết bài tổng quan.

Phân nhóm

• Các test 1-7 thỏa mãn \(N\le100\).
• Các test 8-10 thỏa mãn \(N\le1000\).
• Các test 11-17 thỏa mãn \(N\le10^5\).

Ví dụ

4 0
1 100 2 3

2

4 1
1 100 2 3

3

Giải thích ví dụ 1. Bessie không thể trích dẫn bất kỳ bài báo nào trước đây. Như đã nêu, chỉ số \(h\) của \((1,100,2,3)\) là \(2\).

Giải thích ví dụ 2. Nếu Bessie trích dẫn bài báo thứ ba, các số lượt trích dẫn trở thành \((1,100,3,3)\). Như đã nêu, chỉ số \(h\) của dãy này là \(3\).

Nguồn

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

Tác giả: Dhruv Rohatgi.