409859: GYM103811 C Copy of the String

Charlie and Cara play the same online game in their free time.

In the game, each player has a string with length $$$N$$$ that contains only lowercase letters from the English alphabet. The strength of the player is then calculated by a mysterious function, with the string as the input.

A player is allowed to change their string by paying coins. Two operations can be performed arbitrary times:

1. Reorder all characters with $$$K$$$ coins.
2. Modify a character to its adjacent character, in terms of alphabet, with $$$1$$$ coin. For example, (a, b), (z, y) are pairs of adjacent characters, but (a, c), (a, z) are not.

Charlie has no idea what the mysterious function is, but he noticed that Cara's string $$$S$$$ has been performing very well in the game. Therefore, Charlie decided to copy her string by changing his own string $$$T$$$ using the two given operations.

As a friend of Charlie, you are asked to find the minimum coins Charlie needs to change his string into Cara's string.

The first line contains two integers $$$N$$$ and $$$K$$$. ($$$1 \leq N \leq 5 \times 10^5$$$, $$$0 \leq K \leq 10^9$$$).

The second line contains a string $$$S$$$ with length $$$N$$$.

The third line contains a string $$$T$$$ with length $$$N$$$.

A single integer, the minimum coins Charlie needs in order to change his string into Cara's string.

4 3
dadc
ddcc

4

5 5
feeaf
ffdgc

10