28466번 - 좋은 팀이란?

문제

이번 ICPC 신촌 연합에서는 ICPC 팀연습을 하여 아직 팀을 구하지 못한 사람들을 위해 팀빌딩을 해주기로 한다. 더욱더 좋은 팀을 맞춰주기 위해 개인의 실력과 사주를 고려하여 팀을 짜주기로 하였다. 각 팀의 점수를 계산하여 가장 높은 점수를 만들 방법을 찾고 있다.

개인의 실력은 1ドル$부터 5ドル$까지의 정수 중 하나로 나타낸다.

사주의 일주는 태어난 날에 해당하는 간지를 의미한다. 간지는 “갑을병정무기경신임계”의 10종류의 천간과 “자축인묘진사오미신유술해”의 12종류의 지지의 조합으로 구성되며 “갑자”, “을축”, “병인”, ... , “계해”의 총 60종류가 있다. 편의상 천간의 갑부터 계까지를 각각 0ドル$부터 9ドル$까지의 정수로, 지지의 자부터 해까지를 각각 ‘A’부터 ‘L’까지의 알파벳 대문자로 표현하자. 예를 들어 “갑자”는 “0A”, “계해”는 “9L”로 표현한다.

두 사람의 사주가 잘 맞는지는 천간 관계 점수와 지지 관계 점수로 나타낼 수 있다. 천간 관계 점수는 10ドル \times 10$의 표로, 지지 관계 점수는 12ドル \times 12$의 표로 주어진다.

$X, Y, Z$ 3명의 팀원으로 구성된 팀의 점수는 다음의 항목을 모두 더하여 계산한다.

1. $X$와 $Y$의 천간 관계 점수, 지지 관계 점수
2. $Y$와 $Z$의 천간 관계 점수, 지지 관계 점수
3. $X$와 $Z$의 천간 관계 점수, 지지 관계 점수
4. $X, Y, Z$의 실력 값의 합

사람들의 정보가 모두 주어질 때 세 명을 뽑아 얻을 수 있는 팀의 점수의 최댓값을 구해보자.

입력

첫째 줄에 사람들의 수 $N$이 주어진다. (3ドル \leq N \leq 10^6$)

다음 10ドル$개의 줄에는 줄마다 10ドル$개의 정수로 천간 관계 점수 $a_{ij}$가 공백으로 구분되어 주어진다. (0ドル \le a_{ij} \le 10, a_{ij} = a_{ji}$)

다음 12ドル$개의 줄에는 줄마다 12ドル$개의 정수로 지지 관계 점수 $b_{ij}$가 공백으로 구분되어 주어진다. (0ドル \le b_{ij} \le 10, b_{ij} = b_{ji}$)

다음 $N$개의 줄에 각 사람의 실력 값 $X$와 일주 $S$가 공백으로 구분되어 주어진다. (1ドル \leq X \leq 5,ドル $S$는 위에서 말한 60갑자 중 하나로 주어진다)

출력

첫째 줄에 팀의 점수의 최댓값을 출력한다.

제한

힌트