Bessie has been playing the popular fighting game Moortal Cowmbat for a long time now. However, the game developers have recently rolled out an update that is forcing Bessie to change her play style.

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.

Problem credits: Eric Wei

#4134 upload 4 done 3 how_to_reg 3

Moortal Cowmbat timer 1s memory 512MB

#4134

Moortal Cowmbat 1s 512MB