問題文

$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}$ 以下の相対誤差が生じても解は変わらない

入力

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

$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