题目描述
Problem Background
Xiao Z has ranked sixth in his grade and now needs to catch up with his academic work (whk).
Problem Description
Xiao Z has to study $n$ subjects, and for the $i$-th subject, he has exactly $a_i$ problems to solve. He has unlimited days, and each day he can solve an unlimited number of problems.
Xiao Z considers a day interesting if he solves problems from at least $t$ subjects on that day.
Xiao Z wants to know the maximum number of interesting days he can have.
Input Format
The first line contains two positive integers $n$ and $t$.
The next line contains $n$ integers, representing $a_1, a_2, a_3, \dots, a_{n-1}, a_n$ respectively.
Output Format
Output a single integer, the maximum number of interesting days Xiao Z can have.
Sample Input and Output
Sample Input #1
5 3
3 2 5 1 1
Sample Output #1
3
Sample Input #2
6 4
1 1 4 5 1 4
Sample Output #2
3
Notes/Hints
This problem uses subtask testing.
| Subtask Number | $n\le$ | $a_i\le$ | Special Conditions | Points |
|---|---|---|---|---|
| 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 |
For all data, $1 \le t \le n \le 5\times10^5$, $1 \le a_i \le 10^6$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分