도미노

N이 주어지면, 두 수 (i, j)가 적힌 도미노가 각 1 <= i, j <= N에 대해 하나씩 있어 모두 N^2개이다.

도미노들은 N x N 보드에 놓여 있다. i번째 행, j번째 열에는 (i, j)가 적힌 도미노가 있다.

플레이어는 정확히 N개의 도미노를 골라야 한다. 고른 도미노 중 첫 번째 수가 같은 도미노가 둘 이상 있으면 안 되고, 두 번째 수가 같은 도미노도 둘 이상 있으면 안 된다. 즉, 각 행과 각 열에서 정확히 하나씩 고르는 것과 같다.

고른 도미노들은 하나 이상의 순환 그룹으로 나뉜다. 도미노 (a, b) 뒤에는 첫 번째 수가 b인 도미노를 이을 수 있고, 마지막 도미노의 두 번째 수가 처음 도미노의 첫 번째 수와 같으면 하나의 순환이 된다. (x, x)처럼 두 수가 같은 도미노 하나만으로도 순환 그룹을 이룬다. 위 조건을 만족해 고르면 항상 이러한 순환 분해가 가능하다.

각 도미노의 뒷면에는 점수 계산에 쓰는 값이 적혀 있다. 점수는 고른 도미노들의 뒷면 값을 모두 곱해 구한다. 그 뒤 순환 그룹의 개수가 짝수이면 점수에 -1을 곱한다.

도미노 뒷면의 값이 주어질 때, 만들 수 있는 최소 점수와 최대 점수를 구하라.

첫째 줄에 자연수 N이 주어진다. N은 6 이하이다.

다음 N개의 줄에는 각 줄마다 길이 N인 문자열이 주어진다. i번째 줄의 j번째 문자는 도미노 (i, j)의 뒷면 값이다.

문자는 0부터 9까지의 숫자 또는 A부터 I까지의 대문자이다. 숫자는 그대로 0부터 9까지의 값을 뜻하고, A부터 I까지는 각각 -1부터 -9까지의 값을 뜻한다.

첫째 줄에 얻을 수 있는 최소 점수를 출력한다.

둘째 줄에 얻을 수 있는 최대 점수를 출력한다.