P10184 [YDOI R1] whk

Little Z wants to grind whk.

Little Z needs to grind a total of $n$ subjects. For the $i$-th subject, he has one and only $a_i$ problems. There are infinitely many days available, and each day Little Z can solve infinitely many problems. If Little Z considers a day to be interesting, it is only when on that day he solves problems from **at least** $t$ subjects. Little Z wants to know the maximum number of interesting days.

The first line contains $2$ positive integers $n, t$. The next line contains $n$ integers: $a_1, a_2, a_3, \dots, a_{n-1}, a_n$.

Output one integer, the maximum number of days that Little Z considers interesting.

Subtask 0 is hack testdata and is not scored. **This problem uses bundled tests**. | Subtask ID | $n\le$ | $a_i\le$ | Special property | Score | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $1000$ | $1000$ | None | $20$ | | $2$ | $5\times10^5$ | $10^5$ | $t=1$ | $10$ | | $3$ | $5\times10^5$ | $1$ | All $a_i$ are $1$ | $10$ | | $4$ | $5\times10^5$ | $10^6$ | None | $60$ | Constraints: for all testdata, $1\le t\le n\le 5\times10^5$, $1\le a_i \le 10^6$. Translated by ChatGPT 5