Problem Description

Because of her love for computer science, and the temptation of one day becoming “Dr. Bessie”, the cow Bessie has started pursuing a PhD in computer science. After some time doing research, she has published $N$ papers ($1 \le N \le 10^5$), and her $i$-th paper has received $c_i$ citations from other research papers ($0 \le c_i \le 10^5$).

Bessie has heard that academic achievement can be measured using the $h$-index. The $h$-index is the largest integer $h$ such that the researcher has at least $h$ papers with at least $h$ citations each. For example, if a researcher has $4$ papers with citation counts $(1,100,2,3)$, then the $h$-index is $2$. However, if the citation counts are $(1,100,3,3)$, then the $h$-index would be $3$.

To increase her $h$-index, Bessie plans to write a survey paper and cite some of her own papers in it. Because of page limits, she can cite at most $L$ papers in this survey ($0 \le L \le 10^5$), and she can cite each of her papers at most once.

Please help Bessie find the maximum $h$-index she can achieve after writing this survey.

Note that Bessie’s advisor may tell her that writing a survey purely to increase her $h$-index might be considered academic misconduct; we do not recommend other researchers imitate Bessie’s behavior.

Input Format

The first line contains $N$ and $L$.

The second line contains $N$ space-separated integers $c_1,\ldots,c_N$.

Output Format

Output the maximum $h$-index Bessie can achieve after writing the survey.

4 0
1 100 2 3

2

4 1
1 100 2 3

3

Hint

Sample Explanation 1

Bessie cannot cite any of her previously written papers. As mentioned above, the $h$-index of $(1,100,2,3)$ is $2$.

Sample Explanation 2

If Bessie cites her third paper, the citation counts become $(1,100,3,3)$. As mentioned above, the $h$-index for these citation counts is $3$.

Test Point Properties

• Test points $1-7$ satisfy $N \le 100$.
• Test points $8-10$ satisfy $N \le 1000$.
• Test points $11-17$ satisfy $N \le 10^5$.

Translated by ChatGPT 5