Two Weights

A graph $G$ has $N$ vertices numbered from 0 to $N-1$.

Every edge of $G$ carries two weights, called weight 1 and weight 2.

The cost of a path is $W_1 \times W_2$, where $W_1$ is the sum of the weight 1 values of the edges on the path and $W_2$ is the sum of their weight 2 values. Write a program that finds the cheapest path from vertex 0 to vertex 1.

The first line contains the number of vertices $N$. ($2 \le N \le 20$)

The next $N$ lines describe weight 1, and the $N$ lines after that describe weight 2. Each line is a string of length $N$.

Within a block, character $j$ of line $i$ is the weight of the edge between vertex $i$ and vertex $j$. It is a digit from 1 to 9, or .. A . means there is no edge between those two vertices. Lines and characters are both counted from 0.

Write weight1 for the weight 1 block and weight2 for the weight 2 block. The input satisfies:

• weight1[i][i] = weight2[i][i] = .
• weight1[i][j] = weight1[j][i]
• weight2[i][j] = weight2[j][i]
• if weight1[i][j] is . then weight2[i][j] is ., and the converse holds as well

Print the minimum cost of a path from vertex 0 to vertex 1 on the first line. If vertex 1 cannot be reached from vertex 0, print -1.