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').
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.
ab ab ba 2 1 4 1
4 aba bba