Weird Dissimilarity

Special Judge Time Limit: 4000/2000MS (Java/Others) Memory Limit: 512000/256000KB (Java/Others)

Problem Description

      The issue of this problem is to find out how far two strings over alphabet Z are, with respect to one weird definition of dissimilarity. For any two characters c1 and c2 from Z consider dissimilarity d(c1, c2) of c1 from c2 - non-negative integer number. If we take two strings a and b of equal length l, distance from a to b is 

      You are given two strings s and t. Consider all possible pairs of strings a and b of equal length over Z, such that s is a subsequence of a and t is a subsequence of b (string w of length n is a subsequence of a string v of length m if there exist 1 <= i1 < i2 < ... < in <= m such that w[j] = v[ij] for all 1 <= j <= n). Choose among them a' and b' such that dist(a', b') is minimal possible. Dissimilarity of s from t is defined as D(s, t) = dist(a', b').

      Your task is to find the dissimilarity of s from t and to provide a' and b' such that D(s, t) = dist(a', b').

Input

      The first line of the input file contains Z - several different characters that form the alphabet for the strings we consider (1 <= |Z| <= 200, all characters have ASCII code greater than space).    

      Next two lines contain s and t respectively. Length of each of the given strings does not exceed 2000. Next |Z| lines contain |Z| 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(s, t). On the second and third lines of the output file print a' and b', such that D(s, t) = dist(a', b'), s is a subsequence of a' and t is a subsequence of b'. Length of each of a' and b' must not exceed 4000.

Sample Input

ab
ab
ba
2 1
4 1

Sample Output

4
aba
bba

Source

Andrew Stankevich Contest 3

Manager

Information
Solved Number51
Submit Number187
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel