C. Copy of the String
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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

Examples
Input
4 3
dadc
ddcc
Output
4
Input
5 5
feeaf
ffdgc
Output
10