For a string \(T\) of length between \(1\) and \(3\) consisting of lowercase English letters, define \(P(T)\) by:

• \(P(T_i) := P_i\) for each of \(T_1, T_2, \ldots, T_N\) given by the input;
• \(P(T) := 0\) for each string \(T\) not given as \(T_i\) by the input.

Consider constructing \(S\) by appending a lowercase English letter one by one. When the current \(S\) is \(S = s_1s_2\ldots s_L\), appending a new lowercase English letter \(s'\) increases the beauty of \(S\) increases by:

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

This isn’t true if the length of \(S\) before appending \(s'\) is \(2\) or less, but still we can avoid this case by defining a dummy character $ different from any of a, b, \(\ldots\), z, and push \(2\) dummy characters to the initial \(S\) beforehand (letting the initial \(S\) be \(S = \) $$). For a string \(T\) containing $, let \(P(T) := 0\). Hereinafter, let \(\Sigma := \lbrace\) a, b, \(\ldots\), z \(\rbrace \cup \lbrace\) $ \(\rbrace\).

The delta of the beauty of \(S\), (1), is determined solely by the last two characters of \(S\) before appending, and the new character. Therefore, once you apply the delta of the beauty, you may forget the characters other than the last two characters, as they do not affect the delta of beauty anymore. Thus, we may regard the last two characters as the current “state” to consider:

when the current state is \(s_{L-1}s_L\), appending a lowercase English character \(s'\) to \(S\) increases the beauty by (1), transitioning the state to \(s_L s'\).

This can be represented by the following directed graph:

Let \(c_1c_2\) be the vertex set, which is a string of length \(2\) consisting of characters in \(\Sigma\), and add an edge from each vertex \(c_1c_2\) corresponding to each lowercase English character a, b, \(\ldots\), z. Here, let the weight of the edge corresponding to the lowercase English character \(c'\), which heads to Vertex \(c_2c'\), be \(P(c') + P(c_2c') + P(c_1c_2c')\).

The problem is boiled down to a problem of finding a walk on this graph starting from Vertex $$ with maximum weight (of length at least \(1\)) (or determine that there is a path with infinitely large weight). This can be solved with Bellman-Ford algorithm in a total of \(\mathrm{O}(|\Sigma|^5)\) time.