주사위 스탬프
시간 제한8초메모리 제한512 MB
각 주사위는 정해진 경로를 따라 굴러가며 지나는 칸의 값을 바닥면 숫자로 덮어쓴다. 같은 버튼을 여러 번 눌러도 되며, N번의 선택으로 보드에 남는 숫자 합의 최댓값을 구한다.
문제
당신은 동네 축제에서 지금까지 본 적 없는 게임을 하는 가게를 발견했다. N개의 6면 주사위를 보드 위에 떨어뜨려 굴리는 게임이다. 더 정확히는 N개의 버튼이 N개의 주사위와 1대1로 연결되어 있고, 버튼을 누르면 대응하는 주사위가 보드에 떨어진다. 버튼을 원하는 대로 N번 눌러 주사위를 N번 떨어뜨려 굴려서 점수를 얻는 게임이다.
게임의 더 자세한 규칙을 설명하겠다. 게임에서 쓰는 N개의 주사위는 모두 각 변의 길이가 1인 정육면체이고, 보드는 한 변의 길이가 1인 정사각형 칸으로 나뉜 충분히 넓은 평면이다. 게임을 시작하기 전에 보드의 각 칸에는 모두 0이 쓰여 있다. 각 주사위의 각 면에는 정수가 쓰여 있다. 이는 1부터 6까지라고 보장되지 않으며, 주사위마다 다른 수가 쓰여 있을 수도 있다.
게임에 쓰는 기계에는 N개의 버튼이 달려 있고, N개의 주사위와 1대1로 연결되어 있다. 아무 버튼이나 누르면 대응하는 주사위가 기계에서 배출되어 보드로 떨어지고, 몇 번 회전한다. 회전하는 도중 주사위의 아랫면은 반드시 보드의 어떤 칸에 정확히 겹친다. 아랫면이 칸에 닿을 때마다 그 칸에 쓰여 있던 수가 주사위의 아랫면에 쓰인 수로 덮어쓰인다. 이는 낙하로 처음 보드에 닿을 때도 포함한다. 회전이 멈춘 뒤 주사위는 보드에서 제거되어 원래의 배출 장치로 돌아간다. 버튼을 N번 누른 뒤 보드에 쓰인 수의 합이 최종 점수가 된다. 같은 버튼을 여러 번 누를 수 있지만, 바로 전에 배출한 주사위의 회전이 끝나 배출 장치로 돌아오기 전에는 다음 버튼을 누를 수 없다.
가게 주인은 주사위를 배출하는 방식이 무작위라고 주장하지만, 관찰력이 좋은 당신은 다른 손님이 노는 모습을 지켜보면서 같은 버튼을 눌렀을 때의 동작이 그때까지의 버튼 입력에 관계없이 완전히 동일하다는 것을 알아챘다. 더 구체적으로, i번째 버튼을 눌렀을 때의 동작은 다음과 같이 결정적이다.
i번째 주사위가 배출된다.- 이 주사위는 내부에서 정해진 칸에 정해진 방향으로 떨어진다. 이 방향은 반드시 칸의 정사각형과 아랫면의 정사각형이 정확히 겹치는 방향이다.
- 주사위는 앞뒤좌우 4방향 중 하나로 회전하는 것을 반복한다. 회전 횟수와 각 회전의 방향도 내부에서 정해져 있다.
- 정해진 회전이 끝나면 주사위는 보드에서 제거되어 배출 장치로 돌아간다.
여기서 편의상 3차원 공간을 생각하고, 칸의 변에 평행한 방향으로 각각 x축과 y축을 잡으며, 주사위 윗면이 향하는 방향을 z축 양의 방향으로 둔다. 이때 주사위의 회전은 x, y축의 양, 음 방향 4가지이고, 각각 아래 그림과 같다. 다만 그림 속 기호는 아래 입력 형식에 대응한다.
결정적으로 움직이다니 사기라고 생각했지만, 당신은 N번의 버튼 입력 방식에 따라 최종 점수를 바꿀 수 있다는 것을 깨달았다.
당신은 꼼꼼한 관찰로 각 주사위의 각 면에 쓰인 수, 떨어뜨려지는 초기 위치와 방향, 이후의 회전 방식까지 완전한 정보를 모았다. 모은 정보를 바탕으로, 최선의 버튼 입력 방식으로 얻을 수 있는 이 게임의 최고 점수를 구하라.
입력
입력은 40개 이하의 데이터 세트로 이루어진다. 각 데이터 세트는 다음 형식으로 주어진다.
N
1번째 주사위의 정보
...
N번째 주사위의 정보
입력의 첫 줄은 주사위의 개수를 나타내는 하나의 정수 N으로 이루어진다. 1 ≤ N ≤ 15라고 가정할 수 있다. 이후 N개의 주사위 정보가 이어진다.
각 주사위의 정보는 다음 형식으로 주어진다.
x y
l r f b d u
rot
1번째 줄은 두 정수 x, y로 이루어지며, 배출되었을 때 주사위가 떨어지는 칸의 중심 좌표 (x, y)를 나타낸다. -1,000 ≤ x, y ≤ 1,000이라고 가정할 수 있다.
2번째 줄은 6개의 정수 l, r, f, b, d, u로 이루어지며, 각 면에 쓰인 수를 나타낸다. l, r, f, b, d, u는 각각 떨어졌을 때 x축 음의 방향, x축 양의 방향, y축 음의 방향, y축 양의 방향, z축 음의 방향, z축 양의 방향을 향하는 면에 쓰인 수이다. 1 ≤ l, r, f, b, d, u ≤ 100이라고 가정할 수 있다.
3번째 줄은 회전 방식을 나타내는 문자열 rot으로 이루어진다. rot는 'L', 'R', 'F', 'B'만으로 이루어진 문자열이며, 1글자 이상 30글자 이하이다. rot의 j번째 문자는 j번째 회전의 방향을 나타내고, 문자가 'L', 'R', 'F', 'B'일 때 각각 x축 음의 방향, x축 양의 방향, y축 음의 방향, y축 양의 방향으로 회전함을 나타낸다.
입력의 끝은 하나의 0을 포함한 한 줄로 나타낸다.
출력
각 데이터 세트에 대해, N번의 버튼 입력 방식을 잘 정해 얻을 수 있는 최고 점수를 한 줄로 출력하라. 각 출력 줄은 이 수치 외의 문자를 포함해서는 안 된다.