P9937 [USACO21OPEN] Acowdemia I B

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.

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

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

### 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