P12412 「YLLOI-R1-T1」Waiting for you


The OI training camp is coming, but Little Y's classmates still want to attend school. There are $k$ available classes. Little Y has $n$ good friends, and the $i$-th friend plans to attend $m_i$ of these classes. Since Little Y considers himself too strong, he doesn't attend any classes. If all of Little Y's friends attend the same class, he will be alone in the computer room during that class and feel lonely. His friends want to rearrange their class selections to minimize the number of such lonely classes. Determine the minimum number of lonely classes for Little Y, after optimally rearranging his friends' class choices.

The first line contains two integers, $n$ and $k$. The second line contains $n$ integers, the $i$-th is $m_i$.

Output a single integer — the minimum number of classes during which Little Y will be alone.

### Explanation **Sample 1:** Friend 1 has to attend all $k = 3$ classes, so every class he attends is fixed. If friend 2 attends any class, that class will be attended by both friends, and thus Little Y will be alone during all those classes. So the minimum number of lonely classes is $m_2 = 2$. **Sample 2:** One possible valid arrangement: | | Class 1 | Class 2 | Class 3 | Class 4 | |:---------:|:---------:|:---------:|:---------:|:---------:| | Friend 1 | ✓ | ✓ | ✓ | | | Friend 2 | | ✓ | ✓ | ✓ | | Friend 3 | ✓ | ✓ | | ✓ | Only Class 2 is attended by all three friends, so Little Y is lonely in just that one class. ### Constraints **This problem uses subtask scoring.** - Subtask 1 (20 pts): $n, k \leq 10$. - Subtask 2 (20 pts): $m_1 = 0$. - Subtask 3 (30 pts): $n, k \leq 1000$. - Subtask 4 (30 pts): No additional constraints. For all data: - $1 \leq n \leq 10^6$ . - $1 \leq k \leq 10^9$. - $0 \leq m_i \leq k$.