After another long BedWars session, Muzan and Honey decided to create a highlights video from their match.
They have $$$N$$$ recorded clips, each represented by a string of lowercase English letters.
First, Honey must arrange the clips in any order, using every clip exactly once, and concatenate them into one long replay $$$T$$$.
Before uploading it, Muzan suggests starting the replay from a different moment. For an integer $$$k$$$ with $$$0 \le k \lt |T|$$$, a cyclic shift by $$$k$$$ characters moves the first $$$k$$$ characters of $$$T$$$ to the end. They may choose any such $$$k$$$ to obtain a new replay $$$T'$$$.
For example, if $$$T = \texttt{abcde}$$$, its possible cyclic shifts are:
They are looking for a famous BedWars combo, represented by the string $$$P$$$.
Choose both the order of the clips and the cyclic shift so that the number of linear occurrences of $$$P$$$ as a substring of $$$T'$$$ is maximized. Occurrences are allowed to overlap.
The first line contains an integer $$$N$$$ ($$$1 \le N \le 12$$$), the number of clips.
Each of the next $$$N$$$ lines contains a nonempty string $$$S_i$$$ ($$$1 \le |S_i| \le 50$$$).
The last line contains a nonempty string $$$P$$$ ($$$1 \le |P| \le 50$$$).
All strings contain only lowercase English letters.
Print one integer, the maximum possible number of occurrences of $$$P$$$ after choosing the order of the clips and the cyclic shift.
2baababba
1
The clips are $$$\texttt{baa}$$$ and $$$\texttt{b}$$$. The two possible concatenations are $$$\texttt{baab}$$$ and $$$\texttt{bbaa}$$$, and neither contains $$$\texttt{abba}$$$.
Rotating $$$\texttt{baab}$$$ by two characters gives $$$\texttt{abba}$$$, which contains the target exactly once. Therefore, the answer is $$$1$$$.
