/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 600 点
問題文
N 種類の素材があり、素材 i には A_i の魔力があります。
魔法使いの高橋君は、この中から 1 種類以上を選んで合成し、ポーションを作ろうとしています。
k 種類の素材を合成して出来たポーションの魔力は、合成した直後には素材の魔力の合計であり、時間が 1 経過するごとに k 増加します。 魔力の増加は連続的ではなく離散的であることに注意してください。
高橋君が時刻 0 に 1 度だけ素材の合成を行うとき、魔力がちょうど X のポーションは、最速でいつ手に入りますか？
なお、制約下で魔力がちょうど X のポーションを作れることが証明されます。
制約
- 1 \leq N \leq 100
- 1 \leq A_i \leq 10^7
- 10^9 \leq X \leq 10^{18}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 \ldots A_N
出力
魔力がちょうど X のポーションを手に入れることができる最も早い時刻を出力せよ。
入力例 1
3 9999999999 3 6 8
出力例 1
4999999994
素材 1 と素材 3 を合成して出来たポーションの魔力は、時刻 0 で 3+8=11 であり、時間が 1 経過するごとに 2 増加するので、時刻 4999999994 に 9999999999 になります。これが最速です。
素材 1,2,3 全てを合成して出来たポーションの魔力は、時刻 3333333327 に 9999999998、時刻 3333333328 に 10000000001 となり、ちょうど 9999999999 にはなりません。
入力例 2
1 1000000000000000000 1
出力例 2
999999999999999999
Score : 600 points
Problem Statement
There are N kinds of materials. Material i has a magic power of A_i.
Takahashi, the magician, wants to make a potion by choosing one or more kinds from these materials and mixing them.
At the moment when he makes a potion by mixing k kinds of materials, the magic power of the potion is the sum of the materials used. Then, every second, its magic power increases by k. Note that the increase of the magic power is a discrete - not continuous - process.
Takahashi will mix materials just once, at time 0. What is the earliest time he can get a potion with a magic power of exactly X?
Under the constraints, it can be proved that it is possible to make a potion with a magic power of exactly X.
Constraints
- 1 \leq N \leq 100
- 1 \leq A_i \leq 10^7
- 10^9 \leq X \leq 10^{18}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X A_1 \ldots A_N
Output
Print the earliest time he can get a potion with a magic power of exactly X.
Sample Input 1
3 9999999999 3 6 8
Sample Output 1
4999999994
The potion made by mixing Material 1 and Material 3 has a magic power of 3+8=11 at time 0, and it increases by 2 every second, so it will be 9999999999 at time 4999999994, which is the earliest possible time.
The potion made by mixing all the materials 1, 2, 3 will have a magic power of 9999999998 at time 3333333327 and 10000000001 at time 3333333328, so it will never be exactly 9999999999.
Sample Input 2
1 1000000000000000000 1
Sample Output 2
999999999999999999