14085: Коровакадемія I-Acowdemia I-USACO2021OpenBronze
Бесі навчається на PhD у комп'ютерних науках. Вона опублікувала \(N\) статей (\(1 \leq N \leq 10^5\)) і її \(i\)-у статтю цитували \(c_i\) раз (\(0 \leq c_i \leq 10^5\)).
Бесі чула, що академічні успіхи вимірюються \(h\)-індексом. \(h\)-індекс - це найбільше число \(h\) таке, що вчений має не менше \(h\) статей, кожна з яких цитується не менше \(h\) разів. Наприклад, вчений у якого чотири статті з кількостями цитат \((1,100,2,3)\) має \(h\)-індекс рівний \(2\), а вчений з кількостями цитат (1,100,3,3) має \(h\)-індекс рівний \( 3\).
Щоб підвищити свій \(h\)-індекс Бесі планує написати оглядову статтю, яка цитує деякі з її минулих статей. У зв'язку з обмеженням на кількість сторінок, вона може включити не більше \(L\) цитат у свій огляд (\(0 \leq L \leq 10^5\)), і звичайно вона може процитувати кожну зі своїх статей не більше одного разу.
Допоможіть Бесі визначити максимальний \(h\)-індекс, який вона може досягти написанням своєї оглядової статті.
Зауважимо, що науковий керівник повинен був попередити Бесі, що написання статті виключно з метою збільшення свого \(h\)-індексу сумнівно з етичної точки зору.
Формат вхідних даних
Перший рядок введення містить \(N\) та \(L\).
Другий рядок введення містить \(N\) розділених одиночними пробілами цілих чисел \(c_1,\ldots, c_N\).
Формат вихідних даних
Максимальний \(h\)-індекс, який Бесі може отримати написанням оглядової статті.
Приклад вхідних даних
4 0
1 100 2 3
Приклад вихідних даних
2
Бесі не може цитувати свої статті. Як зазначено раніше її \(h\)-індекс для \((1,100,2,3)\) дорівнює \(2\).
Приклад вхідних даних
4 1
1 100 2 3
Приклад вихідних даних
3
Якщо Бесі процитує третю статтю, її кількості цитувань стануть \((1,100,3,3)\). Як зазначено раніше, \(h\) у цьому випадку дорівнює \(3\).
ОЦІНЮВАННЯ:
- У тестах 1-7 \(N \leq 100\).
- У тестах 8-10 \(N \leq 1000\).
- У тестах 11-17 \(N \leq 10^5\).
Коментарі