L - Next TTPC 3 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

東京工業大学プログラミングコンテストは 1 年に 1 度行われる競技プログラミングのコンテストです。英大文字列 S_1, S_2, S_3, S_4 があり、来年以降、つまり正整数 x に対して x 年後に行われる東京工業大学プログラミングコンテストの略称 T_x は次のようにして決められます。

  • T_x は 4 文字の英大文字からなる文字列である
  • T_x の i 文字目 (1 \le i \le 4) は S_i の ((x - 1) \bmod |S_i|) + 1 文字目と等しい（ |S_i| は文字列 S_i の長さを表す）

正整数 N が与えられます。N 回目に略称が TTPC となるのは何年後でしょうか？

制約

  • 1 \le N \le 10^6
  • 1 \le |S_i| \le 10^3\ (1 \le i \le 4)
  • N は整数
  • S_i は英大文字のみからなる文字列

部分点

  • 追加の制約 |S_i| \leq 50\ (1 \le i \le 4) を満たすデータセットに正解した場合は 15 点が与えられる。

入力

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

N
S_1
S_2
S_3
S_4

出力

以下の 2 つの条件を満たす正整数 x を出力せよ。そのような x が存在しない場合、代わりに -1 を出力せよ。

  • T_x = {}TTPC
  • T_1, T_2, \dots, T_x の中に文字列 TTPC は N 回出現する

入力例 1

3
TTPC
TLE
P
AC

出力例 1

34

1 回目に略称が TTPC となるのは 10 年後、 2 回目に略称が TTPC となるのは 22 年後、 3 回目に略称が TTPC となるのは 34 年後なので、答えは 34 です。

入力例 2

670055
TF
OITFKONTO
GFPPNPWTZP
CCZFB

出力例 2

-1

略称が TTPC となることはありません。

入力例 3

910359
TOKYO
TECH
PROGRAMMING
CONTEST

出力例 3

1401951321