B - Theme Color

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

N 人のクラスがあり、色 1,2,...,M の中から 1 つの色を選んでテーマカラーを決めることとなりました。

それぞれの人が同確率でどれかの色 1 つに投票するとき、色 i(1 \leq i \leq M)r_i 票集まる確率を p とします。

p \geq 10^{-x} を満たす最小の整数 x を求めてください。

ただし、p10^{-6} 以下の相対誤差が生じても x は変わらないことが保証されるものとします。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 0 \leq r_i \leq N
  • r_1+r_2+...+r_M=N
  • 入力は全て整数
  • p10^{-6} 以下の相対誤差が生じても解は変わらない

入力

入力は以下の形式で標準入力から与えられる。

N M
r_1 r_2 ... r_M

出力

p \geq 10^{-x} を満たす最小の整数 x を出力せよ。


入力例 1

3 2
1 2

出力例 1

1

p=0.375 より、p \geq 10^{-x} を満たす最小の整数は 1 となります。


入力例 2

120 5
18 36 31 12 23

出力例 2

8