The Great Mixing Song Festival

Ayeong runs the music show "The Great Mixing Song Festival" at the CHBS network. The show invites singers to perform a new song built by mixing existing songs, and an audience panel picks the best arrangement.

Next week's theme is "mixing the hits of an era". Take the song that ranked first in each year, then combine songs released close in time into one new song. The rules are as follows.

• One mixing uses exactly $c$ different songs.
• Among the songs used in one mixing, the earliest year and the latest year differ by at most $m$.
• Each song is used in at most one mixing. Some songs may be left out entirely.
• The satisfaction of a mixing is the length of the longest melody that every song in that mixing contains. A melody is a run of consecutive notes, that is, a contiguous substring of the string that represents a song. If the songs share no melody at all, the satisfaction is 0.

You are given the song that ranked first in each of the last $N$ years. Ayeong decides how many mixings to make. Maximize the total satisfaction.

The first line contains the number of years of songs $N$ ($1 \le N \le 500$), the largest year difference allowed inside one mixing $m$ ($1 \le m \le 6$), and the number of songs used in one mixing $c$ ($2 \le c \le m + 1$), separated by spaces.

Each of the next $N$ lines contains the melody $S_i$ ($1 \le |S_i| \le 500$) of the song that ranked first in year $i$. Every melody consists only of the lowercase letters a to g, which stand for notes. The song on line $i$ comes from year $i$, so year $i$ and year $j$ differ by $|i - j|$.

Print the maximum possible sum of the satisfactions of the mixings you make.

In the second example the best plan mixes the songs of years 1, 3, 4 into one song and the songs of years 5, 6, 7 into another. The longest common melodies of the two mixings are bcde and bcd, and their lengths add up to 7. The song of year 2 is used in no mixing.