1. Abridged Problem Statement
Given:
- An alphabet Σ of size K.
- Two strings λ and μ.
- A K×K matrix cost[c1][c2] giving a nonnegative “dissimilarity” between characters c1, c2∈Σ.

We seek two strings α,β of equal length L (≤4000) such that λ is a subsequence of α, μ is a subsequence of β, and the position-wise sum of costs
  ∑_{i=1..L} cost[α[i]][β[i]]
is minimized. Output the minimum total cost and one pair (α,β) achieving it.

2. Detailed Editorial

We reduce the problem to a classic 2D DP over prefixes of λ and μ:

Definitions
- Let n=|λ|, m=|μ|.
- Define dp[i][j] = minimum cost achievable when we have already embedded λ[0..i−1] into α and μ[0..j−1] into β, and built α,β to the same length so far.
- We also keep a back-pointer move[i][j]∈{0,1,2} to reconstruct the choices.

Transitions
At state (i,j) we can extend α,β by one more character pair:

  1) Match next characters of both sequences.
     - Append λ[i] to α and μ[j] to β.
     - Cost = dp[i][j] + cost[λ[i]][μ[j]].
     - Go to (i+1,j+1), record move=0.

  2) Advance only in λ: append λ[i] to α and choose the BEST partner char x∈Σ to match in β that minimizes cost[λ[i]][x].
     - Cost = dp[i][j] + min_{x} cost[λ[i]][x].
     - Go to (i+1,j), record move=1.

  3) Advance only in μ: append μ[j] to β and choose the BEST partner char y∈Σ to match in α that minimizes cost[y][μ[j]].
     - Cost = dp[i][j] + min_{y} cost[y][μ[j]].
     - Go to (i,j+1), record move=2.

Precomputations
- Build a map char→index in Σ.
- For every a∈Σ, precompute best_for_a[a] = argmin_b cost[a][b].
- For every b∈Σ, precompute best_for_b[b] = argmin_a cost[a][b].

Complexities
- Precompute best matches in O(K^2).
- DP table has size (n+1)×(m+1), and each cell does O(1) work after precomputations. Total O(n·m + K^2).
- Reconstruct α and β by walking back from (n,m) following move[i][j].

3. C++ Solution
```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;
}
```

4. Python Solution
```python
import sys
def read_tokens():
    return sys.stdin.read().split()

def main():
    tokens = read_tokens()
    it = iter(tokens)
    # 1) Read alphabet, strings
    sigma = next(it)
    lam   = next(it)
    mu    = next(it)
    K = len(sigma)
    n = len(lam)
    m = 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 each character to its index in sigma
    sigma_idx = {c:i for i,c in enumerate(sigma)}

    # 4) Precompute best matches
    best_for_a = [0]*K
    best_for_b = [0]*K
    for a in range(K):
        # find b minimizing cost[a][b]
        best_for_a[a] = min(range(K), key=lambda b: cost[a][b])
    for b in range(K):
        # find a minimizing cost[a][b]
        best_for_b[b] = min(range(K), key=lambda a: cost[a][b])

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

    # 6) Fill DP
    for i in range(n+1):
        for j in range(m+1):
            cur = dp[i][j]
            if cur == INF:
                continue
            # Option 1: match lam[i] with mu[j]
            if i < n and j < m:
                ai = sigma_idx[lam[i]]
                bi = sigma_idx[mu[j]]
                val = cur + cost[ai][bi]
                if val < dp[i+1][j+1]:
                    dp[i+1][j+1] = val
                    move[i+1][j+1] = 0
            # Option 2: advance in lam only
            if i < n:
                ai = sigma_idx[lam[i]]
                bi = best_for_a[ai]
                val = cur + cost[ai][bi]
                if val < dp[i+1][j]:
                    dp[i+1][j] = val
                    move[i+1][j] = 1
            # Option 3: advance in mu only
            if j < m:
                bi = sigma_idx[mu[j]]
                ai = best_for_b[bi]
                val = cur + cost[ai][bi]
                if val < dp[i][j+1]:
                    dp[i][j+1] = val
                    move[i][j+1] = 2

    # 7) Reconstruct alpha, beta by walking back from (n, m)
    i, j = n, m
    alpha = []
    beta  = []
    while i>0 or j>0:
        mv = move[i][j]
        if mv == 0:
            # matched both characters
            alpha.append(lam[i-1])
            beta .append(mu[j-1])
            i -= 1; j -= 1
        elif mv == 1:
            # advanced in lam only
            ai = sigma_idx[lam[i-1]]
            bi = best_for_a[ai]
            alpha.append(lam[i-1])
            beta .append(sigma[bi])
            i -= 1
        else:
            # advanced in mu only
            bi = sigma_idx[mu[j-1]]
            ai = best_for_b[bi]
            alpha.append(sigma[ai])
            beta .append(mu[j-1])
            j -= 1

    # Reverse because we built them backwards
    alpha.reverse()
    beta .reverse()

    # 8) Print results
    out = []
    out.append(str(dp[n][m]))
    out.append(''.join(alpha))
    out.append(''.join(beta))
    sys.stdout.write("\n".join(out))

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

5. Compressed Editorial
Use a 2D DP dp[i][j] over prefixes of λ,μ. Three moves—match both next chars, or advance one string (inserting the other’s best-match character)—all cost O(1) after precomputing best partners per alphabet symbol. Reconstruct the optimal α,β via back-pointers. Total time O(|λ|·|μ|+|Σ|²).
