#USACO21OPENST3. 学术诚信(integrity)

学术诚信(integrity)

题目背景

原题为 P7557 [USACO21OPEN] Acowdemia S

academic adj. 学业的,学术的

integrity n. 正直,诚信

希望同学们在学习上要遵守学术诚信规则,做一个实事求是的人。

注意题面中 Gooby 的行为有违反学术道德的嫌疑,请同学们未来不要模仿。

题目描述

Gooby 喜欢计算机科学,他希望能够成为「计算机科学博士」。所以他开始攻读计算机科学博士学位。经过一段时间的学术研究,他已经发表了 NN 篇论文(1N1051 \leq N \leq 10^5),并且他的第 ii 篇论文得到了来自其他研究文献的 cic_i 次引用(0ci1050 \leq c_i \leq 10^5)。

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

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

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

输入格式

输入的第一行包含 NNKKLL

第二行包含 NN 个空格分隔的整数 c1,,cNc_1,\ldots, c_N

输出格式

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

输入输出样例 #1

输入 #1

4 4 1
1 100 1 1

输出 #1

3

输入 #2

4 1 4
1 100 1 1

输出 #2

2

说明/提示

样例说明

对于第一个样例,Gooby 可以写至多四篇综述,每一个综述最多引用一篇文章。如果 Gooby 引用他的第一、第三篇论文各两次,他的 hh 指数会变为 33

对于第二个样例,Gooby 可以写至多一篇综述。如果 Gooby 引用他的第一、第三、第四篇论文中的任意一篇,他的 hh 指数会变为 22

测试点性质:

  • 测试点 161 \sim 6 满足 N100N\le 100
  • 测试点 7167 \sim 16 没有额外限制。