<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

214. Weird Dissimilarity
time limit per test: 0.5 sec.
memory limit per test: 65536 KB
input: standard
output: standard



The issue of this problem is to find out how far two strings over alphabet Σ are, with respect to one weird definition of dissimilarity. For any two characters c1 and c2 from Σ consider dissimilarity d(c1, c2) of c1 from c2 — non-negative integer number. If we take two strings α and beta of equal length l, distance from α to β is dist(α, β) = sum(i=1..l, d(α[i], β[i])).

You are given two strings λ and μ. Consider all possible pairs of strings α and β of equal length over Σ, such that λ is a subsequence of α and μ is a subsequence of β (string ω of length n is a subsequence of a string ξ of length m if there exist 1 ≤ i1 < i2 < ... < i_n ≤ m such that ω[j] = ξ[ij] for all 1 ≤ j ≤ n). Choose among them α' and β' such that dist(α', β') is minimal possible. Dissimilarity of λ from μ is defined as D(λ, μ) = dist(α', β').

Your task is to find the dissimilarity of λ from μ and to provide α' and β' such that D(λ, μ) = dist(α', β').

Input

The first line of the input file contains Σ — several different characters that form the alphabet for the strings we consider (1 ≤ |Σ| ≤ 200, all characters have ASCII code greater than space). Next two lines contain λ and μ respectively. Length of each of the given strings does not exceed 2000. Next |Σ| lines contain |Σ| non-negative integer numbers each, j-th number of i-th line contains dissimilarity of i-th character from j-th.

Output

On the first line of the output file print D(λ, μ). On the second and third lines of the output file print α' and β', such that D(λ, μ) = dist(α', β'), λ is a subsequence of α' and μ is a subsequence of β'. Length of each of α' and β' must not exceed 4000.

Sample test(s)

Input
ab
ab
ba
2 1
4 1

Output
4
aba
bba
Author:	Andrew Stankevich
Resource:	Petrozavodsk Summer Trainings 2003
Date:	2003-08-30

<|response|>
1. Abridged Problem Statement  
You are given:  
- An alphabet Σ of size K (characters are distinct).  
- Two strings λ (length n) and μ (length m) over Σ.  
- A K×K non‐negative integer matrix cost, where cost[a][b] is the dissimilarity of character a from b.  

We seek two strings α and β of the **same length L ≤ 4000** such that:  
- λ is a subsequence of α, and μ is a subsequence of β.  
- The total cost ∑_{i=1..L} cost[α[i]][β[i]] is **minimized**.  

Output the minimum total cost and one pair (α, β) achieving it.

2. Key Observations  
- **DP on prefixes**: Let dp[i][j] be the minimum cost after embedding λ[0..i−1] into α and μ[0..j−1] into β, building α and β to equal length so far.  
- **Three transition types** from state (i, j):  
  1. **Match both next characters**: append λ[i] to α and μ[j] to β, cost += cost[λ[i]][μ[j]], move to (i+1, j+1).  
  2. **Advance λ only**: append λ[i] to α and choose the best partner x∈Σ for it in β, i.e. x=minimizes cost[λ[i]][x], move to (i+1, j).  
  3. **Advance μ only**: append μ[j] to β and choose the best partner y∈Σ for it in α, i.e. y=minimizes cost[y][μ[j]], move to (i, j+1).  
- **Best partner precomputation**: For each character a in Σ, precompute best_b[a] = argmin_b cost[a][b]; similarly best_a[b] = argmin_a cost[a][b]. This makes transitions O(1).  
- **Back‐pointers**: Store which of the three moves was taken at each dp[i][j], so you can reconstruct α and β by walking backward from (n, m).

3. Full Solution Approach  
Let n = |λ|, m = |μ|, K = |Σ|.  

Preprocessing:  
  a. Map each character of Σ to an index 0…K−1.  
  b. Read the cost matrix cost[K][K].  
  c. For each a∈[0..K−1], compute best_b[a] = argmin_{b} cost[a][b].  
     For each b∈[0..K−1], compute best_a[b] = argmin_{a} cost[a][b].  

DP Initialization:  
  - Create dp array of size (n+1)×(m+1), initialize all entries to +∞ except dp[0][0] = 0.  
  - Create move array of same size to record which transition was chosen (0 = match both, 1 = advance λ only, 2 = advance μ only).  

DP Recurrence:  
For i from 0..n, for j from 0..m, if dp[i][j] is finite:  
 1. If i < n and j < m:  
    newCost = dp[i][j] + cost[ idx(λ[i]) ][ idx(μ[j]) ]  
    if newCost < dp[i+1][j+1], update dp[i+1][j+1] and move[i+1][j+1]=0.  
 2. If i < n:  
    let a = idx(λ[i]), b = best_b[a]  
    newCost = dp[i][j] + cost[a][b]  
    if newCost < dp[i+1][j], update dp[i+1][j] and move[i+1][j]=1.  
 3. If j < m:  
    let b = idx(μ[j]), a = best_a[b]  
    newCost = dp[i][j] + cost[a][b]  
    if newCost < dp[i][j+1], update dp[i][j+1] and move[i][j+1]=2.  

Reconstruction of α and β:  
  - Start from (i, j) = (n, m).  
  - While (i>0 or j>0):  
    • If move[i][j]==0, prepend λ[i−1] to α and μ[j−1] to β, then i--, j--.  
    • If move[i][j]==1, prepend λ[i−1] to α and Σ[ best_b[idx(λ[i−1])] ] to β, then i--.  
    • If move[i][j]==2, prepend Σ[ best_a[idx(μ[j−1])] ] to α and μ[j−1] to β, then j--.  
  - The constructed α and β are the optimal solution.  

Time complexity: O(K² + n·m). Memory: O(n·m). n,m≤2000 so 4 million states is within 0.5 s in optimized C++.  

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (ll)4e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1) Read alphabet Σ and input strings λ, μ
    string sigma, lam, mu;
    cin >> sigma >> lam >> mu;
    int K = sigma.size();
    int n = lam.size();
    int m = mu.size();

    // 2) Read cost matrix
    vector<vector<int>> cost(K, vector<int>(K));
    for(int i = 0; i < K; i++){
        for(int j = 0; j < K; j++){
            cin >> cost[i][j];
        }
    }

    // 3) Map each character in Σ to its index 0..K-1
    vector<int> idx(256, -1);
    for(int i = 0; i < K; i++){
        idx[(unsigned char)sigma[i]] = i;
    }

    // 4) Precompute best partners
    // best_b[a] = argmin_b cost[a][b]
    // best_a[b] = argmin_a cost[a][b]
    vector<int> best_b(K), best_a(K);
    for(int a = 0; a < K; a++){
        int mn = INT_MAX, arg = 0;
        for(int b = 0; b < K; b++){
            if(cost[a][b] < mn){
                mn = cost[a][b];
                arg = b;
            }
        }
        best_b[a] = arg;
    }
    for(int b = 0; b < K; b++){
        int mn = INT_MAX, arg = 0;
        for(int a = 0; a < K; a++){
            if(cost[a][b] < mn){
                mn = cost[a][b];
                arg = a;
            }
        }
        best_a[b] = arg;
    }

    // 5) DP and back-pointer arrays
    vector<vector<ll>> dp(n+1, vector<ll>(m+1, INF));
    vector<vector<int>> move(n+1, vector<int>(m+1, -1));
    dp[0][0] = 0;

    // 6) Fill DP table
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            ll cur = dp[i][j];
            if(cur == INF) continue;

            // Option 1: match lam[i] with mu[j]
            if(i < n && j < m){
                int a = idx[(unsigned char)lam[i]];
                int b = idx[(unsigned char)mu[j]];
                ll nc = cur + cost[a][b];
                if(nc < dp[i+1][j+1]){
                    dp[i+1][j+1] = nc;
                    move[i+1][j+1] = 0;
                }
            }
            // Option 2: advance λ only
            if(i < n){
                int a = idx[(unsigned char)lam[i]];
                int b = best_b[a];
                ll nc = cur + cost[a][b];
                if(nc < dp[i+1][j]){
                    dp[i+1][j] = nc;
                    move[i+1][j] = 1;
                }
            }
            // Option 3: advance μ only
            if(j < m){
                int b = idx[(unsigned char)mu[j]];
                int a = best_a[b];
                ll nc = cur + cost[a][b];
                if(nc < dp[i][j+1]){
                    dp[i][j+1] = nc;
                    move[i][j+1] = 2;
                }
            }
        }
    }

    // 7) Reconstruct α and β from back-pointers
    int i = n, j = m;
    string A, B;
    while(i > 0 || j > 0){
        int mv = move[i][j];
        if(mv == 0){
            // matched both
            A.push_back(lam[i-1]);
            B.push_back(mu[j-1]);
            i--; j--;
        }
        else if(mv == 1){
            // advanced λ only
            int a = idx[(unsigned char)lam[i-1]];
            int b = best_b[a];
            A.push_back(lam[i-1]);
            B.push_back(sigma[b]);
            i--;
        }
        else {
            // advanced μ only
            int b = idx[(unsigned char)mu[j-1]];
            int a = best_a[b];
            A.push_back(sigma[a]);
            B.push_back(mu[j-1]);
            j--;
        }
    }
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());

    // 8) Output answer
    cout << dp[n][m] << "\n";
    cout << A << "\n" << B << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
def main():
    data = sys.stdin.read().split()
    it = iter(data)

    # 1) Read Σ, λ, μ
    sigma = next(it)
    lam   = next(it)
    mu    = next(it)
    K = len(sigma)
    n, m = len(lam), len(mu)

    # 2) Read cost matrix
    cost = [ [0]*K for _ in range(K) ]
    for i in range(K):
        for j in range(K):
            cost[i][j] = int(next(it))

    # 3) Map characters to indices
    idx = { c:i for i,c in enumerate(sigma) }

    # 4) Precompute best partners
    best_b = [ min(range(K), key=lambda b: cost[a][b]) for a in range(K) ]
    best_a = [ min(range(K), key=lambda a: cost[a][b]) for b in range(K) ]

    # 5) Initialize DP and move tables
    INF = 10**18
    dp = [ [INF]*(m+1) for _ in range(n+1) ]
    move = [ [ -1 ]*(m+1) for _ in range(n+1) ]
    dp[0][0] = 0

    # 6) Compute DP
    for i in range(n+1):
        for j in range(m+1):
            cur = dp[i][j]
            if cur == INF: continue

            # match both
            if i < n and j < m:
                a = idx[lam[i]]
                b = idx[mu[j]]
                val = cur + cost[a][b]
                if val < dp[i+1][j+1]:
                    dp[i+1][j+1] = val
                    move[i+1][j+1] = 0

            # advance λ only
            if i < n:
                a = idx[lam[i]]
                b = best_b[a]
                val = cur + cost[a][b]
                if val < dp[i+1][j]:
                    dp[i+1][j] = val
                    move[i+1][j] = 1

            # advance μ only
            if j < m:
                b = idx[mu[j]]
                a = best_a[b]
                val = cur + cost[a][b]
                if val < dp[i][j+1]:
                    dp[i][j+1] = val
                    move[i][j+1] = 2

    # 7) Reconstruct α, β
    i, j = n, m
    A, B = [], []
    while i > 0 or j > 0:
        mv = move[i][j]
        if mv == 0:
            A.append(lam[i-1])
            B.append(mu[j-1])
            i, j = i-1, j-1
        elif mv == 1:
            a = idx[lam[i-1]]
            b = best_b[a]
            A.append(lam[i-1])
            B.append(sigma[b])
            i -= 1
        else:
            b = idx[mu[j-1]]
            a = best_a[b]
            A.append(sigma[a])
            B.append(mu[j-1])
            j -= 1
    A.reverse()
    B.reverse()

    # 8) Print results
    sys.stdout.write(str(dp[n][m]) + "\n")
    sys.stdout.write("".join(A) + "\n")
    sys.stdout.write("".join(B) + "\n")

if __name__ == "__main__":
    main()
```