長さ \(1\) 以上 \(3\) 以下の英小文字のみからなる文字列 \(T\) について \(P(T)\) を、

• 入力で与えられている各 \(T_1, T_2, \ldots, T_N\) については \(P(T_i) := P_i\) とし、
• 入力で \(T_i\) として与えられていない文字列 \(T\) については \(P(T) := 0\) とします。

文字列 \(S\) の末尾に英小文字を \(1\) 文字ずつ付け加えていくことによって \(S\) を作っていくことを考えます。 現在の \(S\) が \(S = s_1s_2\ldots s_L\) のとき、その末尾に新たにある英小文字 \(s'\) を追加すると、\(S\) の美しさが追加前と比べて

\[P(s') + P(s_Ls') + P(s_{L-1}s_Ls') \tag{1}\]

だけ増加します。 \(s'\) を追加する前の \(S\) の長さが \(2\) に満たないケースではこれは成り立ちませんが、a, b, \(\ldots\), z のどれとも異なるダミーの文字 $ を用意し、初期状態の \(S\) に予めのダミー文字を \(2\) つ入れておけば（つまり、初期状態の \(S\) を \(S = \) $$ とする）、追加前の \(S\) の長さが \(2\) に満たないケースは回避できます。 このとき、$ を含む文字列 \(T\) については \(P(T) := 0\) とします。 以下、\(\Sigma := \lbrace\) a, b, \(\ldots\), z \(\rbrace \cup \lbrace\) $ \(\rbrace\) とします。

\(S\) の美しさの増加分 (1) は、追加前の \(S\) の末尾 \(2\) 文字と新たに追加する一文字のみから定まります。 よって、一度美しさの加算を終えてしまえば、\(S\) の末尾 \(2\) 文字以外の部分は今後の美しさの増加分に影響しないため忘れてしまっても良いです。 そこで、\(S\) の末尾 \(2\) 文字のみを現在の「状態」とみなすことで、

現在の状態が \(s_{L-1}s_L\) のとき、\(S\) に英小文字 \(s'\) を追加すると美しさが (1) だけ増加し、状態が \(s_L s'\) に遷移する

と考えることができます。 このことは、以下の重み付き有向グラフで表現することができます。

\(\Sigma\) 上の長さ \(2\) の文字列 \(c_1c_2\) を頂点とし、 各頂点 \(c_1c_2\) から英小文字 a, b, \(\ldots\), z それぞれに対応する辺を張る。このとき、英小文字 \(c'\) に対応する辺は頂点 \(c_2c'\) への重み \(P(c') + P(c_2c') + P(c_1c_2c')\) の辺とする。

本問題は、このグラフの上での頂点 $$ を始点とする重み最大の（長さ \(1\) 以上の）ウォークを求める（あるいはいくらでも重みの大きいウォークが存在すると判定する）問題となります。 これは Bellman-Ford 法によって \(\mathrm{O}(|\Sigma|^5)\) 時間で解くことができます。