2715 - 优秀论文

题目描述

小H 开始攻读博士学位。经过一段时间的努力,他已经发表了 N 篇论文(1 \leq N \leq 10^5),并且他的第 i 篇论文得到了来自其他研究文献的 c_i 次引用(0 \leq c_i \leq 10^5)。

小H 听说学术成就可以用 h 指数来评价。h 指数等于使得研究员有至少 h 篇引用次数不少于 h 的论文的最大整数 h。例如,如果一名研究员有 4 篇论文,引用次数分别为 (1,100,2,3),则 h 指数为 2,然而若引用次数为 (1,100,3,3)h 指数将会是 3

为了提升他的 h 指数,小H 计划写至多 K 篇综述(0 \leq K \leq 10^5),并在每篇综述中引用许多他曾经写过的论文。然而,由于页数限制,他至多可以在一篇综述中引用 L 篇论文(0 \leq L \leq 10^5)。当然,一篇综述中他只能引用一篇论文至多一次(但是一篇论文可以在多篇综述中被引用)。

请帮助 小H 求出在写完这些综述后他可以达到的最大 h 指数。小H 不可以在一篇综述中引用他写的其他综述。

当然我们并不推崇这种刷数据的行为,请大家不要向 小H 学习。

输入

输入的第一行包含 NKL

第二行包含 N 个空格分隔的整数 c_1,\ldots, c_N

输出

输出最大可以达到的 h 指数。

样例

输入

4 4 1
1 100 1 1

输出

3
说明

样例说明

在这个样例中,小H 可以写至多一篇综述。如果 小H 引用他的第一、第三、第四篇论文中的任意一篇,他的 h 指数会变为 2

测试点性质:

  • 测试点 1 \sim 6 满足 N\le 100
  • 测试点 7 \sim 16 没有额外限制。
来源

USACO 2021 US Open, Silver

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 33
通过人数 14
金币数量 1 枚
难度 基础


上一题 下一题