두 가중치

정점이 $N$개인 그래프 $G$가 있다. 정점에는 0번부터 $N-1$번까지 번호가 매겨져 있다.

$G$의 모든 간선에는 가중치가 두 개씩 붙어 있고, 각각을 가중치 1, 가중치 2라고 한다.

경로의 비용은 경로에 있는 간선의 가중치 1을 모두 더한 값 $W_1$과 가중치 2를 모두 더한 값 $W_2$를 곱한 $W_1 \times W_2$이다. 0번 정점에서 1번 정점으로 가는 경로 중 비용이 가장 작은 경로를 찾는 프로그램을 작성하시오.

첫째 줄에 정점의 수 $N$이 주어진다. ($2 \le N \le 20$)

다음 $N$개 줄에는 가중치 1의 정보가, 그다음 $N$개 줄에는 가중치 2의 정보가 주어진다. 각 줄은 길이가 $N$인 문자열이다.

한 블록에서 $i$번째 줄의 $j$번째 문자는 정점 $i$와 정점 $j$를 잇는 간선의 가중치이며, 1부터 9까지의 숫자 또는 .이다. 문자가 .이면 두 정점 사이에 간선이 없다. 줄과 문자는 모두 0번부터 센다.

가중치 1의 정보를 weight1, 가중치 2의 정보를 weight2라고 하면 다음이 성립한다.

• weight1[i][i] = weight2[i][i] = .
• weight1[i][j] = weight1[j][i]
• weight2[i][j] = weight2[j][i]
• weight1[i][j]가 .이면 weight2[i][j]도 .이고, 그 역도 성립한다.

첫째 줄에 0번 정점에서 1번 정점으로 가는 경로의 비용 중 최솟값을 출력한다. 0번 정점에서 1번 정점으로 갈 수 없으면 -1을 출력한다.