주사위 쌓기

천수는 여러 종류의 주사위를 아래에서 위로 차례대로 쌓으려 한다. 모든 주사위는 같은 크기의 정육면체이고, 여섯 면에는 1부터 6까지의 수가 하나씩 적혀 있다. 마주 보는 두 면의 수의 합이 반드시 7일 필요는 없다.

주사위는 1번부터 N번까지 순서대로 쌓는다. 서로 맞닿은 두 주사위에서, 아래 주사위의 윗면에 적힌 수와 위 주사위의 아랫면에 적힌 수가 같아야 한다. 1번 주사위는 처음에 어떤 방향으로 놓아도 된다.

쌓은 주사위들은 긴 사각 기둥을 이룬다. 기둥에는 위에서 아래까지 이어지는 네 개의 옆면이 있다. 각 주사위는 윗면과 아랫면을 유지한 채 옆으로 90도, 180도, 270도 돌릴 수 있다. 따라서 한 주사위의 윗면과 아랫면이 정해지면, 나머지 네 면 중 어떤 수든 목표로 하는 옆면에 오도록 회전할 수 있다. 네 옆면 중 한 옆면에 적힌 수들의 합이 최대가 되도록 쌓았을 때, 그 최댓값을 구하시오.

첫 줄에 주사위의 개수 N이 주어진다. 다음 N개의 줄에는 1번 주사위부터 N번 주사위까지 각 주사위의 여섯 면에 적힌 수가 주어진다. 한 줄의 여섯 수는 아래 전개도에서 A, B, C, D, E, F 위치의 순서이다. 이 전개도에서 마주 보는 위치는 A-F, B-D, C-E이다.

N은 10,000 이하이다. 같은 종류의 주사위가 여러 번 주어질 수 있다.

그림 1

가능한 한 옆면의 합 중 최댓값을 첫 줄에 출력한다.