<|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
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int64_t inf = numeric_limits<int64_t>::max();

string sigma, lambda, mu;
vector<vector<int>> cost;

void read() {
    cin >> sigma >> lambda >> mu;
    cost.assign(sigma.size(), vector<int>(sigma.size()));
    cin >> cost;
}

void solve() {
    // We can solve this problem by creating a dp with states (i, j), meaning
    // that the strings alpha and beta already contain lambda[:i] and mu[:j]
    // respectively. Then we have 3 options for the transition:
    //
    //    1) We add lambda[i] to alpha and mu[j] to beta at the given cost. This
    //       moves both i and j by 1.
    //
    //    2) We add lambda[i] to alpha and the best character based on the cost
    //       matrix for lambda[i]. This doesn't move j.
    //
    //    3) We add mu[j] to beta and the best character based on the cost
    //    matrix
    //       for mu[j]. This doesn't change i. This is a quadratic DP.
    //
    // We will precompute the best characters so that this lookup is O(1). The
    // answer is dp[|lambda|][|mu|], but we will also maintain a table
    // opt_move[i][j] equal to 0, 1, 2 (so int8_t is fine to not blowup memory),
    // meaning which of the above 3 moves was taken to arrive to (i, j). We use
    // this to recover the strings. Overall the complexity is O(|sigma|^2 +
    // |lambda| * |mu|).

    int n = lambda.size();
    int m = mu.size();
    int k = sigma.size();

    vector<int> sigma_idx(256, -1);
    for(int i = 0; i < k; i++) {
        sigma_idx[sigma[i] + 128] = i;
    }

    vector<int> best_for_a(k);
    vector<int> best_for_b(k);

    for(int i = 0; i < k; i++) {
        int min_cost = numeric_limits<int>::max();
        for(int j = 0; j < k; j++) {
            if(cost[i][j] < min_cost) {
                min_cost = cost[i][j];
                best_for_a[i] = j;
            }
        }
    }

    for(int j = 0; j < k; j++) {
        int min_cost = numeric_limits<int>::max();
        for(int i = 0; i < k; i++) {
            if(cost[i][j] < min_cost) {
                min_cost = cost[i][j];
                best_for_b[j] = i;
            }
        }
    }

    vector<vector<int64_t>> dp(n + 1, vector<int64_t>(m + 1, inf));
    vector<vector<int8_t>> opt_move(n + 1, vector<int8_t>(m + 1, -1));

    dp[0][0] = 0;

    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            if(dp[i][j] == inf) {
                continue;
            }

            if(i < n && j < m) {
                int a_idx = sigma_idx[lambda[i] + 128];
                int b_idx = sigma_idx[mu[j] + 128];
                int64_t new_cost = dp[i][j] + cost[a_idx][b_idx];
                if(new_cost < dp[i + 1][j + 1]) {
                    dp[i + 1][j + 1] = new_cost;
                    opt_move[i + 1][j + 1] = 0;
                }
            }

            if(i < n) {
                int a_idx = sigma_idx[lambda[i] + 128];
                int best_b = best_for_a[a_idx];
                int64_t new_cost = dp[i][j] + cost[a_idx][best_b];
                if(new_cost < dp[i + 1][j]) {
                    dp[i + 1][j] = new_cost;
                    opt_move[i + 1][j] = 1;
                }
            }

            if(j < m) {
                int b_idx = sigma_idx[mu[j] + 128];
                int best_a = best_for_b[b_idx];
                int64_t new_cost = dp[i][j] + cost[best_a][b_idx];
                if(new_cost < dp[i][j + 1]) {
                    dp[i][j + 1] = new_cost;
                    opt_move[i][j + 1] = 2;
                }
            }
        }
    }

    string alpha, beta;
    int i = n, j = m;

    while(i > 0 || j > 0) {
        int move = opt_move[i][j];

        if(move == 0) {
            alpha = lambda[i - 1] + alpha;
            beta = mu[j - 1] + beta;
            i--;
            j--;
        } else if(move == 1) {
            int a_idx = sigma_idx[lambda[i - 1] + 128];
            int best_b = best_for_a[a_idx];
            alpha = lambda[i - 1] + alpha;
            beta = sigma[best_b] + beta;
            i--;
        } else {
            int b_idx = sigma_idx[mu[j - 1] + 128];
            int best_a = best_for_b[b_idx];
            alpha = sigma[best_a] + alpha;
            beta = mu[j - 1] + beta;
            j--;
        }
    }

    cout << dp[n][m] << "\n";
    cout << alpha << "\n";
    cout << beta << "\n";
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation
```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()
```
