問題文

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

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

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

ただし、p に 10^{-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
• 入力は全て整数
• p に 10^{-6} 以下の相対誤差が生じても解は変わらない

入力例 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