You have multiset of
n strings of the same length, consisting of lowercase English letters. We will say that those strings are easy to remember if for each string there is some position
i and some letter
c of the English alphabet, such that this string is the only string in the multiset that has letter
c in position
i.
For example, a multiset of strings {"abc", "aba", "adc", "ada"} are not easy to remember. And multiset {"abc", "ada", "ssa"} is easy to remember because:
-
the first string is the only string that has character c in position 3;
-
the second string is the only string that has character d in position 2;
-
the third string is the only string that has character s in position 2.
You want to change your multiset a little so that it is easy to remember. For
aij coins, you can change character in the
j-th position of the
i-th string into any other lowercase letter of the English alphabet. Find what is the minimum sum you should pay in order to make the multiset of strings easy to remember.