Comparing Strings

Interview

Time limit1sMemory limit512 MB

Summary

Given two lowercase strings, align them by repeating characters of either string, keeping order, and minimize the sum of absolute alphabet-position differences over aligned pairs.

Level: Medium6 of 10
Topics: Dynamic programming, String, Array, Implementation
Solved: No attempts yet

Problem

We want to find the minimum difference between two strings, where the method for comparing two strings follows the two rules below.

First, the difference between each pair of characters equals the absolute value of the difference in their positions in the alphabet. For example, a is the first letter and c is the third letter, so the difference between a and c is |1-3| = 2. Similarly, the difference between a and z is |1 - 26| = 25.

Second, it is possible to stretch each letter of the two strings. Using the two rules above, the sum of the character-wise differences between the two strings gives the difference between the strings. For example, given apple and aple, you can stretch the p in aple to make apple. In this case the difference between the two strings is 0.

Given any two strings, find the minimum possible difference between the two strings.

When computing the sum of the character-wise differences between the two strings, you must make the lengths of the two strings equal first.

Input

The first line gives N and M, the lengths of the two strings. (1 ≤ N, M ≤ 300)

The second line gives the first string.

The third line gives the second string.

The strings contain only lowercase letters from a to z.

Output

Find the minimum difference between the two strings.

Examples2

Example 1
Input
```
5 4
apple
apla
```
Expected output
```
4
```
Example 2
Input
```
14 12
aaaappppppplle
applllllleee
```
Expected output
```
0
```