B - 2525文字列分解

Time Limit: 2.525 sec / Memory Limit: 252.525 MB

配点 : 300

問題文

dwango社員のニワンゴくんは2525SNSという新しいSNSを開発しています。 2525SNSは2525文字列のみ投稿可能な画期的なSNSです。

この問題において、251 回以上の繰り返しで表される文字列を2525文字列と呼びます。 例えば、25,2525,2525252525252525 などは2525文字列ですが、空文字列や 2255,2552,252 などは2525文字列ではありません。

まず、ニワンゴくんは2525文字列をいくつか作ることにしました。 ニワンゴくんは手元にあった文字列 s1 つ以上の部分列に分解し、分解された部分列それぞれが2525文字列となるようにしたいです。

最小でいくつの部分列に分解すればこれを達成可能ですか?どのように分解しても達成不可能な場合は -1 を出力してください。分解についてはサンプル 1 の説明も参照してください。

制約

  • 1 \leq |s| \leq 2{,}525
  • s25 のみからなる

入力

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

s

出力

答えを出力せよ。


入力例 1

225525

出力例 1

2
  • 1 つの部分列に分解した場合、225525 は2525文字列ではないため条件を満たしません。
  • その他の分解としては例えば (25,2525) となるような分解と (25,25,25) となるような分解が考えられます。それぞれについて正しい分解の例とそうでない例を示します。各部分列内において、s における相対的な出現順序が守られるように分解する必要があることに注意してください。
  • (25,2525) となるように 2 つの部分列に分解することで、それぞれの部分列が2525文字列となるように分解できます。
062c9a95edb82917811ef52962f98a3e.png

入力例 2

52

出力例 2

-1
  • 分解方法は 2 通りありますが、それぞれの部分列が2525文字列となるように分解することはできません。
  • 52 に分解したのち、それぞれの順序を入れ替えて 25 を作ることは不可能なことに注意してください。

入力例 3

2255252252222555552522255255

出力例 3

5

入力例 4

25252

出力例 4

-1