E - Super Lucky Sequence

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

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

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

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

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

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

• 入力はすべて整数

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

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

3 13 2
1 7

3

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

10 6 2
1 2

10

7 18 1
4

-1

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

125 2 1
3

-1

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