No tags yet

No tag edit access

time limit per test: 0.5 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: 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 c_{1} and c_{2} from Σ consider *dissimilarity* d(c_{1}, c_{2}) of c_{1} from c_{2} — 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 ≤ i_{1} < i_{2} < ... < i_n ≤ m such that ω[j] = ξ[i_{j}] 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(α', β').

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 ≤ i

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

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.

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.

Input

ab

ab

ba

2 1

4 1

ab

ba

2 1

4 1

Output

4

aba

bba

aba

bba

Author: | Andrew Stankevich |

Resource: | Petrozavodsk Summer Trainings 2003 |

Date: | 2003-08-30 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/15/2019 23:19:58 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|