Minimum String Alignment Distance

Given two non-empty strings \(A\) and \(B\) and an integer constant \(K\), we define an extension of a string as any string obtained by inserting any number of space characters (denoted by \(\verb| \|\)) at the beginning, end, or between the characters of the original string.

For example, if \(X = \verb|abcbcd|\), then strings such as \(\verb|abcb cd|\), \(\verb| a bcbcd |\), and \(\verb|abcb cd |\) are all extensions of \(X\>.

Now, suppose \(A_1\) is an extension of \(A\) and \(B_1\) is an extension of \(B\) having the same length. Their distance is defined as the sum over each position of the following cost:

• If both characters are non-space, the cost is \(|\text{ASCII}(\text{char}_A)-\text{ASCII}(\text{char}_B)|\).
• If one character is a space and the other is not, the cost is \(K\).
• If both are spaces, the cost is \(0\).

Among all pairs of extensions \(A_1\) and \(B_1\) of \(A\) and \(B\) respectively (such that they have equal length), there exists a pair whose alignment cost is minimized. This minimal cost is defined as the distance between strings \(A\) and \(B\).

Your task is to compute this minimum distance given \(A\), \(B\) and \(K\). This is analogous to a sequence alignment problem with a gap penalty of \(K\) and a mismatch cost defined by the absolute difference of the ASCII values.

inputFormat

The input consists of three lines. The first line contains an integer (K) (the cost for aligning a space with a non-space character). The second line contains the string (A). The third line contains the string (B). Both strings consist of visible characters without any spaces.

outputFormat

Output a single integer representing the minimum distance between strings (A) and (B) computed based on the given rules.

sample

3
abc
abd

1