E - Super Lucky Sequence

2 secs 1024 MB
Yourein

Statement


Yourein君は夢で神に会いました。
神は個の相異なる0以上9以下の整数からなる集合をYourein君に手渡しこう言いました。
「あなたは今日条件を満たす数列を持つと幸せになれる」

神が示した条件は以下の通りでした

  • 数列の項はすべて集合の要素である。
  • 数列の初項がでない。
  • その数列は初項から末項までをつなげて10進数整数としたときにの倍数である。(「この条件の例は入力例1や3を参照すること」)

Yourein君は神のお告げを信じそのような数列を紙に書いて1日持ち歩くことにしました。

Yourein君は数列の長さが長いほうがより幸せになれると考えており、紙には最大で項の数列を書くスペースがあります。そのため、項数が項以下かつ条件をすべて満たす数列のうち最も長いものを紙に書こうと考えています。

Yourein君が最終的に紙に書き込んだ数列の長さを教えて下さい。
ただし、どのようにしても条件を満たす数列を作ることができない場合は-1を出力してください

Constraints


  • 入力はすべて整数

Input


1行目にがスペースを開けて与えられる 2行目にが与えられる。


Output


問題文の条件に合うような数列のうち最も項数が多いものの項数を出力せよ。ただし、そのような数列を作ることができない場合は-1を出力せよ。

Examples


Example1


input1
3 13 2
1 7
output1
3

作れる数列はです。 この中で13の倍数となるものとしてはがあります。
その長さは3なので3を出力します。

Example2


input2
10 6 2
1 2
output2
10

Example3


input3
7 18 1
4
output3
-1

実はの倍数です。このように求める数列が構成可能な場合でも書ききるスペースがなければ答えがとなることに気をつけてください。

Example4


input4
125 2 1
3
output4
-1

をいくつ並べてもそれらはすべての倍数です。またの位も偶数にはならないので、どのようにしても条件を満たす数列を構成することができません。

Submit


Go (1.14)