n, m = map(int, input().split()) s = input().strip() t = input().strip() INF = float('inf') # Initialize DP tables M = [[INF] * (m + 1) for _ in range(n + 1)] D = [[INF] * (m + 1) for _ in range(n + 1)] I = [[INF] * (m + 1) for _ in range(n + 1)] M[0][0] = 0 # Base case for i in range(n + 1): for j in range(m + 1): # Compute M[i][j] if i > 0 and j > 0: replace_cost = 0 if s[i-1] == t[j-1] else 5 min_prev = min(M[i-1][j-1], D[i-1][j-1], I[i-1][j-1]) M[i][j] = min_prev + replace_cost # Compute D[i][j] (deletions) if i > 0: candidates = [] if M[i-1][j] != INF: candidates.append(M[i-1][j] + 9) if D[i-1][j] != INF: candidates.append(D[i-1][j] + 2) if candidates: D[i][j] = min(candidates) # Compute I[i][j] (insertions) if j > 0: candidates = [] if M[i][j-1] != INF: candidates.append(M[i][j-1] + 9) if I[i][j-1] != INF: candidates.append(I[i][j-1] + 2) if candidates: I[i][j] = min(candidates) # Determine the minimal cost min_cost = min(M[n][m], D[n][m], I[n][m]) # Backtrack to find the alignment s1 = [] s2 = [] i, j = n, m current = None if min_cost == M[n][m]: current = 'M' elif min_cost == D[n][m]: current = 'D' else: current = 'I' while i > 0 or j > 0: if current == 'M': s1.append(s[i-1]) s2.append(t[j-1]) replace_cost = 0 if s[i-1] == t[j-1] else 5 prev_val = M[i][j] - replace_cost i -= 1 j -= 1 # Find previous state if i >= 0 and j >= 0: if M[i][j] == prev_val: current = 'M' elif D[i][j] == prev_val: current = 'D' else: current = 'I' elif current == 'D': s1.append(s[i-1]) s2.append('-') current_val = D[i][j] i -= 1 # Determine previous state if i >= 0: candidate1 = M[i][j] + 9 candidate2 = D[i][j] + 2 if current_val == candidate1: current = 'M' elif current_val == candidate2: current = 'D' else: current = None # Error case, should not happen elif current == 'I': s1.append('-') s2.append(t[j-1]) current_val = I[i][j] j -= 1 # Determine previous state if j >= 0: candidate1 = M[i][j] + 9 candidate2 = I[i][j] + 2 if current_val == candidate1: current = 'M' elif current_val == candidate2: current = 'I' else: current = None # Error case, should not happen # Reverse to get the correct order s1.reverse() s2.reverse() aligned_s = ''.join(s1) aligned_t = ''.join(s2) print(min_cost) print(aligned_s) print(aligned_t)