## USACO 2019 December Contest, Gold

## Problem 3. Moortal Cowmbat

Contest has ended.

**Log in to allow submissions in analysis mode**

The game uses $M$ buttons labeled by the first $M$ lowercase letters ($1 \leq M \leq 26$). Bessie's favorite combo of moves in the game is a length-$N$ string $S$ of button presses ($1 \leq N \leq 10^5$). However, due to the most recent update, every combo must now be made from a series of "streaks", where a streak is defined as a series of the same button pressed at least $K$ times in a row ($1 \leq K \leq N$). Bessie wants to modify her favorite combo to produce a new combo of the same length $N$, but made from streaks of button presses to satisfy the change in rules.

It takes $a_{ij}$ days for Bessie to train herself to press button $j$ instead of button $i$ at any specific location in her combo (i.e. it costs $a_{ij}$ to change a single specific letter in $S$ from $i$ to $j$). Note that it might take less time to switch from using button $i$ to an intermediate button $k$ and then from button $k$ to button $j$ rather than from $i$ to $j$ directly (or more generally, there may be a path of changes starting with $i$ and ending with $j$ that gives the best overall cost for switching from button $i$ ultimately to button $j$).

Help Bessie determine the smallest possible number of days she needs to create a combo that supports the new requirements.

#### SCORING:

- Test cases 2-4 satisfy $N\le 1000, K\le 50.$
- Test cases 5-8 satisfy $N\le 30,000, K\le 50.$

#### INPUT FORMAT (file cowmbat.in):

The first line of input contains $N$, $M$, and $K$. The second line contains $S$, and the final $M$ lines contain an $M\times M$ matrix of values $a_{ij}$, where $a_{ij}$ is an integer in the range $0 \ldots 1000$ and $a_{ii} = 0$ for all $i$.#### OUTPUT FORMAT (file cowmbat.out):

Output a single number, representing the minimum number of days Bessie needs to change her combo into one that satisfies the new requirements.#### SAMPLE INPUT:

5 5 2 abcde 0 1 4 4 4 2 0 4 4 4 6 5 0 3 2 5 5 5 0 4 3 7 0 5 0

#### SAMPLE OUTPUT:

5

The optimal solution in this example is to change the a into b, change the d into e, and then change both e’s into c’s. This will take $1+4+0+0=5$ days, and the final combo string will be bbccc.

Problem credits: Eric Wei