No.1808 Fullgold Alchemist
タグ : / 解いたユーザー数 155
作問者 :
MasKoaTS
/ テスター :
Problem Statement
There are $N$ types of ores numbered $1,2, \dots ,N$, and there are $A_{1},A_{2}, \dots ,A_{N}$ pieces of them, respectively.
The alchemist Koa performs the following action on them any number of times, $0$ or more: "freely choose either one of the following $2$ types of operations and execute it".
Choose $1$ pair of integers $(i,j)$ satisfying $1 \leq i < j \leq N$, consume $1$ piece of ore $i$, and produce $1$ piece of ore $j$.
Consume $M$ pieces each of ores $1,2, \dots ,N$ and produce $1$ gold nugget.
What is the maximum number of gold nuggets Koa can produce?
Constraints
$1 \leq N \leq 2 \times 10^{5}$
$1 \leq M \leq 10^{9}$
$0 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
All input values are integers.
Input
The input is given in the following format.
$N$ $M$
$A_{1}$ $A_{2}$ $\cdots$ $A_{N}$
Line $1$ contains $N$ and $M$ in this order, separated by half-width spaces.
Line $2$ contains $A_{1},A_{2},\dots,A_{N}$ in this order, separated by half-width spaces.
Output
Print the answer on $1$ line, followed by a newline.
Sample
Sample 1
Input
4 3 5 3 1 3
Output
1
After repeating the operation of consuming $1$ piece of ore $1$ to produce $1$ piece of ore $3$ a total of $2$ times, consuming $3$ pieces each of ores $1, 2, 3, 4$ produces $1$ gold nugget.
It is not possible to produce $2$ or more gold nuggets.
Sample 2
Input
10 2 9 8 7 6 5 4 3 2 1 0
Output
2
Sample 3
Input
7 10 0 100 100 100 100 100 100
Output
0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。