DNA 점수

DNA 문자열은 A, C, T, G로만 이루어진 문자열이다. 길이가 같은 두 DNA 문자열 X, Y의 DNA 점수는 각 위치 i에 대해 Score(X_i, Y_i)를 모두 더한 값이다. Score는 네 DNA 문자를 행과 열로 갖는 4×4 정수 점수판이다.

점수판은 다음 조건을 모두 만족해야 한다.

1. 모든 원소는 -10 이상 10 이하의 정수이다.
2. 점수판은 주대각선을 기준으로 대칭이다: Score(X, Y) = Score(Y, X).
3. 모든 대각 원소는 양수이다: Score(X, X) > 0.
4. 점수판의 16개 원소의 합은 0이다.

길이가 같은 N개의 DNA 문자열이 주어진다. 서로 다른 두 문자열을 고르는 N(N-1)/2개의 모든 쌍에 대해 DNA 점수를 계산할 때, 그 평균이 최대가 되도록 점수판을 정할 수 있다. 가능한 평균의 최댓값을 구하시오.

첫째 줄에 DNA 문자열의 개수 N이 주어진다. N은 50 이하의 자연수이다.

둘째 줄부터 N개의 줄에 DNA 문자열이 하나씩 주어진다. 모든 문자열의 길이는 같고, 길이의 최댓값은 50이다.

가능한 DNA 점수 평균의 최댓값을 출력한다. 절대 오차 또는 상대 오차가 10^-2 이하이면 정답으로 인정된다.

첫 번째 공개 테스트에서는 Score(A, A)와 Score(A, C)를 모두 10으로 둘 수 있다. 그러면 나머지 원소도 조건을 만족하도록 정할 수 있고, 세 문자열 쌍의 DNA 점수가 모두 30이 된다.