問題

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

制約

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

入力

N  MN \space\space M
A1  A2  ...  ANA_1 \space\space A_2 \space\space ... \space\space A_N

出力

求める値を11行で答えよ。

サンプル

入力1
5 3
1 2 2 2 0
出力1
3

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

入力2
10 2 
0 1 0 2 0 2 1 1 1 0
出力2
4

Submit


Go (1.21)