GreatPower

問題

あなたは長さ$N$の数列と$2$以上の整数$M$を持っており、数列の$i$番目の値は$M^{A_i}$です。 あなたは数列の中から1個以上のいくつかの要素を選び、それらの和を取ることで$M^K(Kは非負整数)$となる値を作ります。このときに達成できる最大の$K$を求めてください。

制約

• $1 \leq N \leq 2・10^5$
• $2 \leq M \leq 10^9$
• $0 \leq A_i \leq 10^9$
• 入力は全て整数である

入力

$N \space\space M$
$A_1 \space\space A_2 \space\space ... \space\space A_N$

出力

求める値を$1$行で答えよ。

サンプル

5 3
1 2 2 2 0

3

数列の値は$[3, 9, 9, 9, 1]$です。$2,3,4$番目の値を足し合わせることで$27=3^3$を作ることができ、これが作れる最大の数なので答えは$3$となります。

10 2 
0 1 0 2 0 2 1 1 1 0

4