문자열의 확장과 거리

문자열 X의 확장이란, X의 임의의 위치(맨 앞과 맨 뒤 포함)에 공백을 원하는 개수(0개, 1개, 또는 그 이상)만큼 끼워 넣어 만든 문자열을 말한다. 예를 들어 X가 'abcbcd'이면 'abcb-cd', '-a-bcbcd-', 'abcd-cd-' 등은 모두 X의 확장이다. (여기서 공백은 '-'로 나타낸다.)

A1을 문자열 A의 확장, B1을 문자열 B의 확장이라 하자. A1과 B1의 길이가 같다면 두 문자열 사이의 거리를 정의할 수 있는데, 이는 같은 위치에 있는 두 문자의 거리를 모두 더한 값이다. 두 문자 사이의 거리는 두 문자의 ASCII 코드 값의 차이이며, 공백과 (공백이 아닌) 다른 문자 사이의 거리는 입력으로 주어지는 K이다.

두 문자열 A와 B가 주어질 때, 길이가 같은 확장 A1과 B1을 잘 골라 두 문자열 사이의 거리를 가장 작게 만들었을 때 그 최소 거리를 구하는 프로그램을 작성하시오.

첫째 줄에 문자열 A, 둘째 줄에 문자열 B가 주어진다. 두 문자열은 모두 알파벳 소문자로만 이루어져 있으며, 길이는 2000 이하이다. 셋째 줄에는 공백과 다른 문자 사이의 거리 K가 주어진다. (1 ≤ K ≤ 100)

첫째 줄에 가능한 가장 작은 거리를 출력한다.