시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB40713910736.770%

문제

이번 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갑자 중 하나로 주어진다)

출력

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

예제 입력 1

4
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 5
0 0 0 0 0 0 0 0 0 0 5 0
0 0 0 0 0 0 0 0 0 5 0 0
0 0 0 0 0 0 0 0 5 0 0 0
0 0 0 0 0 0 0 5 0 0 0 0
0 0 0 0 0 0 5 0 0 0 0 0
0 0 0 0 0 5 0 0 0 0 0 0
0 0 0 0 5 0 0 0 0 0 0 0
0 0 0 5 0 0 0 0 0 0 0 0
0 0 5 0 0 0 0 0 0 0 0 0
0 5 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0
2 0A
3 3B
4 7B
1 9L

예제 출력 1

14

출처

Camp > ICPC Sinchon Algorithm Camp > 2023 ICPC Sinchon Summer Algorithm Camp Contest > 초급 D번