题目描述

由于对计算机科学的热爱，以及有朝一日成为 「Bessie 博士」的诱惑，奶牛 Bessie 开始攻读计算机科学博士学位。经过一段时间的学术研究，她已经发表了 N 篇论文（1≤N≤105），并且她的第 i 篇论文得到了来自其他研究文献的 ci​ 次引用（0≤ci​≤105）。

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

为了提升她的 h 指数，Bessie 计划写一篇综述，并引用一些她曾经写过的论文。由于页数限制，她至多可以在这篇综述中引用 L 篇论文（0≤L≤105），并且她只能引用每篇她的论文至多一次。

请帮助 Bessie 求出在写完这篇综述后她可以达到的最大 h 指数。

注意 Bessie 的导师可能会告知她纯粹为了提升 h 指数而写综述存在违反学术道德的嫌疑；我们不建议其他学者模仿 Bessie 的行为。

输入格式

输入的第一行包含 N 和 L。

第二行包含 N 个空格分隔的整数 c1​,…,cN​。

输出格式

输出写完综述后 Bessie 可以达到的最大 h 指数。

输入输出样例

输入 #1

4 0
1 100 2 3

输出 #1

2

输入 #2

4 1
1 100 2 3

输出 #2

3

说明/提示

样例解释 1

Bessie 不能引用任何她曾经写过的论文。上文中提到，(1,100,2,3) 的 h 指数为 2。

样例解释 2

如果 Bessie 引用她的第三篇论文，引用数会变为 (1,100,3,3)。上文中提到，这一引用数的 h 指数为 3。

测试点性质

• 测试点 1−7 满足 N≤100。
• 测试点 8−10 满足 N≤1000。
• 测试点 11−17 满足 N≤105。

【代码示例】

#include <bits/stdc++.h>
using namespace std;
int n, m, c[100005];

bool chk(int x) {
	int sum = 0;
	int mm = m;
	for (int i = 1; i <= n; i++) {
		if (c[i] >= x)
			sum++;
		if (c[i] == x - 1 && mm > 0) {
			sum++;
			mm--;
		}
	}
	return sum >= x;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> c[i];
	//if(m<=n) c[n+1]=m;
	//else c[n+1]=n;
	int l = 1, r = 1e5, ans = -1;

	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (chk(mid)) {
			l = mid + 1;
			ans = mid;
		} else
			r = mid - 1;
	}
	cout << ans << endl;
}