No.3297 Bake Cookies
Problem Statement
There are $N$ ovens numbered from $1$ to $N$, and $M$ pieces of cookie dough.
The $i$-th piece of dough takes $1$ minute to bake in oven $A_i$, and $T$ minutes to bake in any other oven.
An oven can bake only $1$ piece of dough at a time.
Find the minimum time required to bake all the pieces of dough.
Note that the time for putting dough into an oven and the like is not taken into account.
Constraints
- $1 \leq N, M \leq 2 \times 10^{5}$
- $1 \leq T \leq 10^{9}$
- $1 \leq A_i \leq N$
- All inputs are integers.
Input
The input is given from standard input in the following format.
$N$ $M$ $T$ $A_1$ $A_2$ $\cdots$ $A_M$
Output
Output the answer to the problem on a single line.
Sample
Sample 1
Input
2 6 2 1 1 1 1 1 2
Output
4
For example, if oven $1$ bakes the $1, 2, 3, 4$-th pieces of dough and oven $2$ bakes the $5, 6$-th pieces of dough, all the pieces of dough can be baked in $4$ minutes.
It is impossible to bake all the pieces of dough in less than $4$ minutes, so output $4$.
Sample 2
Input
1 10 100 1 1 1 1 1 1 1 1 1 1
Output
10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
sepa38
くらげ