007 - 文字列の町(The town of String)

時間制限 8 秒 / メモリ制限 512 MB / 得点 80 / x 0 /

TLE
8sec
MLE
512MB
得点
80

ストーリー

町 $MAM\_MOTH$ は、断崖絶壁である( $OHTSUNO\_ZIKA$ 町と似ている(似てないです)…)。

この町は、超最新機器、「どこでもテレポータ」(どこでも移動できるとは言ってない)がないと移動できない、
神のみが許される土地だ。




いくらマンモスが神としてあがめられても、ナウマンゾウのほうが神なため(真実)



さて、異論は認めないが話はここまでにしよう…ね…

問題

町 $MAM\_MOTH$ は、縦 $H$ マス横 $W$ マスにタワー状の土地が切り立っている。
一つ一つのマスが切り離されているため、徒歩では移動することができない。

土地の上に「どこでもテレポータ」(以下テレポータ)と石像に彫られた文字 $C_i$ が $1$ 個ずつ有ることがある。
これは町に $N$ 個だけ存在する。

テレポータは、現在位置の列、行のテレポータのある土地(斜め移動はダメ)で、
現在の標高 $E_i$ と同じ場合移動ができる。
それに加えて、
現在の土地の標高よりも低いテレポータのある土地の中で一番高い土地だけ移動できるか
現在の土地の標高よりも高いテレポータのある土地の中で一番低い土地だけ移動できる。
これはテレポータに与えられる値　$D_i$ が $0$ だと前者、 $1$ だと後者となる。
ただしそのような土地が存在しない場合は移動できない。
これは行と列で、独立して適応される。
つまり、$D_i = 0$ ならば、行の中で低い土地の中の高い土地、列の中で低い土地の中の高い土地を二つ見つけるような感じだ。

ナウ人間くんがいた。ナウ人間は、やっぱり任意の土地にヘリコプターから落下してくるようだ。

ナウ人間くんは土地を移動するとき、
そこにある文字を必ず左から順にメモして文字列を作っていく。一度移動したところの文字はもう書けない。

閉路ができているようなところ、具体的には任意の $2$ つの位置 $u$ , $v$ があったとき、
経路を通って必ず $u$ から　$v$ へ到達できるようなところは一つの結界としてみることができる。
結界となったところは、自由に並び替えた部分文字列としてメモすることができる。
ただし結界は一つの石像があるのと同義としてみるため、
一回部分文字列をメモしたらその結界の使用していない部分文字列を再びどこかで使用することはできない。

現在とある文字列 $T$ の部分文字列と同じとなるようなメモした部分文字列の文字数の最大を見つけようとしています。

部分文字列とは、文字列の任意の連続した区間の文字列とする(つまり文字列そのものでもよい)。

課題

ナウ人間君が適切に移動したときに、文字列 $T$ の部分文字列と同じメモした部分文字列の文字数の最大を求めよ。

入力

$1$ 行目に文字列 $T$ が与えられる。

$2$ 行目に縦 $H$ , 横 $W$ , テレポータと石像がある土地の数 $N$ が与えられる。

$3$ 〜 $N + 2$ 行目に、
テレポータと石像がある土地の座標 $X_i$ , $Y_i$ , 標高 $E_i$ , 石像に彫られた文字 $C_i$ , テレポータに与えられる値 $D_i$ が与えられる。

$T$
$H$ $W$ $N$
$X_1$ $Y_1$ $E_1$ $C_1$ $D_1$
$X_2$ $Y_2$ $E_2$ $C_2$ $D_2$
      .
      .
      .
$X_N$ $Y_N$ $E_N$ $C_N$ $D_N$

出力

ナウ人間君が適切に移動したときに、文字列 $T$ の部分文字列と同じメモした部分文字列の文字数の最大を出力せよ。

制約

  • 与えられる値は全て整数であることが保証される。
  • $1 \leq |T| \leq 1000$ ($||$は文字列の長さを示す)
  • $1 \leq N \leq min(1000, H \times W)$
  • $1 \leq X_i \leq W \leq 1000$
  • $1 \leq Y_i \leq H \leq 1000$
  • $1 \leq E_i \leq 10^9$
  • $D_i$ は $0$ もしくは $1$ である。
  • $C_i$ と $T$ の中身の文字は小文字のアルファベットである。
  • $i \neq j$ のとき、 $X_i = X_j$ かつ $Y_i = Y_j$ にならない。

入出力例

入力例1

astringyeah
5 7 12
3 1 31 s 0
5 1 25 i 0
7 1 24 t 1
5 2 27 r 0
7 2 26 n 1
3 3 29 r 0
5 3 28 i 0
6 3 27 t 0
3 4 30 a 0
6 4 27 b 1
1 4 26 n 1
1 5 27 g 1

出力例1

5

解説

$1$ 番目の地点を始点とする。

このとき、 $2$ 番目の地点と $9$ 番目の地点に移動することが可能である。今回は $2$ 番目のほうへ移動する。

$2, 3, 4, 5$ 番目のノードは閉路であるため、並び替えて文字列を作ることができる。

$1$ 番目の 's' と、 $2, 3, 4, 5$ 番目の "trin" で、 strinを作ることができ、したがって最大の文字数は $5$ である。

コメント

君は文字になれるか。