시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 113 44 40 63.492%

문제

두 문자열을 비교하는 방법이 다음과 같은 두 가지 규칙을 따를 때, 두 문자열 간 차이의 최솟값이 얼마가 되는지를 구해보려 한다. 첫 번째로 각 문자 간의 차이는 알파벳 순서의 차이의 절댓값과 같다. 예를 들어, a는 첫 번째 알파벳이고 c는 세 번째 알파벳이므로, a와 c의 차이는 |1-3| = 2이다. 마찬가지로 a와 z의 차이는 |1 - 26| = 25이다. 두 번째 규칙은 두 문자열의 각 알파벳을 늘이는 것이 가능하다는 것이다. 위 두 규칙을 이용해 두 문자열의 문자 간 차이의 합을 구하면 문자열의 차이가 된다. 예를 들어 apple과 aple이 주어질 때, aple의 p를 늘려 apple로 만들 수 있다. 이 경우 두 문자열의 차이는 0이다. 임의의 두 문자열이 주어질 때, 두 문자열의 차이가 최소가 되는 값을 구해라.

단, 두 문자열에서 문자 간의 차이의 합을 구할 때는 반드시 두 문자열의 길이를 동일하게 만들어서 계산해야 한다.

입력

첫 번째 줄에는 2개의 문자열의 길이인 NM가 주어진다. (1 ≤ N, M ≤ 300)

두 번째 줄에는 첫 번째 문자열이 주어진다.

세 번째 줄에는 두 번째 문자열이 주어진다.

단, 문자열에는 a~z까지의 알파벳 소문자만 주어진다.

출력

두 문자열 간 차이의 최솟값을 구한다.

예제 입력 1

5 4
apple
apla

예제 출력 1

4

예제 입력 2

14 12
aaaappppppplle
applllllleee

예제 출력 2

0