Treasure Chest Password

The treasure chest has a password consisting of \(n\) digits. When these digits are concatenated, they form a string of length \(n\). For each digit position \(i\) (\(1 \le i \le n\)), there is a set \(s_i\) representing the possible digits that can be used at that position.

In addition, A has already tried \(k\) password combinations \(d_1, d_2, \dots, d_k\) (note that these tried combinations are not necessarily restricted to the corresponding set \(s_i\)). All of these attempts have failed.

A now wants to know the maximum number of additional attempts he would need in the worst-case scenario to eventually find the correct password. More formally, let the total number of valid passwords be \(\prod_{i=1}^{n} |s_i|\) and let \(T\) be the count of already tried combinations that are valid (i.e. for every \(i\), the \(i\)th digit of the attempt belongs to \(s_i\)). Then if \(\prod_{i=1}^{n} |s_i| > T\), the answer is \(\prod_{i=1}^{n} |s_i| - T\); otherwise, if no valid password remains, output \(-1\).

inputFormat

The first line contains two integers \(n\) and \(k\) separated by a space.

The next \(n\) lines each contain a string representing the set \(s_i\) of allowed digits for the \(i\)th position. Each character in the string is a digit which is allowed in that position.

Then the following \(k\) lines each contain a string of length \(n\) representing a password combination that has already been tried.

outputFormat

Output a single integer: the maximum number of additional attempts needed to eventually guess the password in the worst-case scenario. If it is impossible to ever guess the correct password (i.e. no valid candidate remains), output \(-1\).

sample

3 2
123
45
678
158
456

17