User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

56.5% (13/23)

Description

俗話說:「三個臭皮匠勝過一個諸葛亮!」這時候塔矢亮不開心了!

在小嵐村(小嵐當村長的時候改的名字)中有 $N$ 個臭皮匠,當很多個臭皮匠的 IQ 相加的時候,確實有可能比諸葛亮的 IQ 還高。
所以塔矢亮決定對臭皮匠做降智打擊,以下有兩種降智打擊的操作。

  • 指定一個 臭皮匠,讓他的 IQ 減一
  • 指定兩個不同的臭皮匠 A & B,讓 A 去模仿 B,使得 A 的 IQ 跟 B 的 IQ 一樣

若諸葛亮的 IQ 為 $K$,初始小蘭村中的臭皮匠 IQ 為 $a_i, 1\leq i \leq n$,請問塔矢亮最少需要進行幾次操作,才能夠使得臭皮匠們的 IQ 總和不大於諸葛亮的 IQ

Input Format

第一行有兩個整數 $N, K$,$1 \leq N \leq 2 \cdot 10^5, 1 \leq K \leq 10^{15}$。
第二行有 $N$ 個整數 $a_i,1\leq i \leq n$,$1 \leq a_i \leq 10^9$。

Output Format

輸出一個整數,此整數為塔矢亮需要進行的操作數量!

Sample Input 1

1 110
120

Sample Output 1

10

Sample Input 2

2 169
66 99

Sample Output 2

0

Sample Input 3

10 1
2 2 3 1 1 7 1 7 7 7

Sample Output 3

7

Hints

第 3 個範例的操作如下:
先將 $a_4$ 減一,執行 $3$ 次,此時 $a_4 = -2$,
接著選擇 $a_6, a_8, a_9, a_{10}$ 讓他們跟 $a_4$ 一樣,共 $4$ 次操作。
得到 $a = [2, 2, 3, -2, 1, -2, 1, -2, -2, -2]$

感謝各位這學期的配合,新年快樂~

Subtasks

No. Testdata Range Score
1 0~13 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1