벽돌

Josefine은 bricks라는 테트리스와 비슷한 게임을 하고 있다. 이 게임은 $6$개의 열 $\times \; 8$개의 행으로 이루어진 직사각형 격자에서 진행된다. 벽돌 하나는 격자의 $1 \times 1$칸을 차지한다. 처음에 격자는 비어 있다. 벽돌 모양은 일부가 벽돌로 채워져 있고 나머지는 공기인 직사각형이다. 다음은 $4 \times 3$ 벽돌 모양의 예시이며, 여기서 $\#$는 벽돌을 나타내고 $\_$는 공기를 나타낸다:

  #_##
  ##__
  #__#

게임은 $N$개의 라운드에 걸쳐 진행된다. 각 라운드에서 플레이어에게 벽돌 모양 하나가 주어지며, 플레이어는 이를 격자의 위쪽에서 떨어뜨릴 가로 방향 위치를 결정해야 한다. 벽돌 모양을 떨어뜨리면 각 벽돌은 서로 독립적으로 수직선을 따라 아래로 떨어지며, 격자의 바닥이나 다른 벽돌(같은 모양에 속한 벽돌 또는 이전 라운드의 벽돌) 바로 위에 놓인다. 벽돌은 서로 독립적으로 떨어지므로, 이후에는 한 열의 벽돌 사이에 공기 구멍이 생기지 않는다(이는 테트리스와 다르다). 벽돌 모양을 떨어뜨리기 전에 플레이어는 이를 $0$, $90$, $180$, 또는 $270$도 회전할 수 있다. 모든 벽돌이 격자 내부에 놓이도록 벽돌 모양을 떨어뜨려야 한다.

각 라운드가 끝날 때, 격자에서 적어도 $3$개의 벽돌이 있는 모든 열은 무너지며, 그에 따라 해당 벽돌들은 격자에서 제거된다. 라운드 $i$에는 라운드 점수 $s_i$가 대응된다. 라운드 $i$에서 무너진 벽돌의 수를 $b_i$라고 하면, 플레이어는 해당 라운드에서 $b_i \cdot s_i$점을 얻는다.

게임의 목표는 모든 라운드에서 얻는 총점을 최대화하는 것이다(즉, $\Sigma_{i=1}^{N} b_i s_i$를 최대화한다). 주어진 $N$개의 벽돌 모양과 라운드 점수로 얻을 수 있는 최대 점수를 계산하는 프로그램을 작성하여 Josefine을 도와주자.

채점

여러 테스트 그룹으로 구성된 테스트 세트로 제출한 풀이를 검사한다. 한 그룹의 점수를 받으려면 해당 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한 조건

$1$ | $30$ | $N \leq 5$

$2$ | $70$ | 추가 제한 조건 없음.

입력의 첫 번째 줄에는 라운드의 수를 나타내는 정수 $N$ ($1 \leq N \leq 300$)가 주어진다.

이후 $N$개 라운드 각각에 대한 정보가 주어진다. 각 라운드의 첫 번째 줄에는 정수 $w_i, h_i, s_i$ ($1 \leq w_i, h_i \leq 6$, $0 \leq s_i \leq 10000$)가 주어지며, 각각 라운드 $i$의 벽돌 모양의 너비와 높이, 그리고 라운드 $i$의 라운드 점수를 나타낸다. 이어지는 $h_i$개의 줄에는 각각 길이가 $w_i$이고 $\#$(벽돌) 또는 $\_$(공기)로 구성된 문자열이 주어지며, 라운드 $i$의 벽돌 모양을 나타낸다. 이 직사각형은 항상 모양의 모든 벽돌을 덮는 가능한 가장 작은 직사각형이다.

가능한 최대 점수를 정수로 출력한다.

첫 번째 벽돌 모양을 회전하지 않고 가능한 한 왼쪽으로 떨어뜨리기만 하면 다음과 같다:

  ______
  ______
  ______
  ______
  ______
  ______
  #_____
  ##____

그런 다음 두 번째 벽돌 모양을 반시계 방향으로 $90$도 회전하고 가능한 한 왼쪽으로 떨어뜨리면 다음과 같다: (Xs는 무너진 벽돌을 표시하며, 다음 라운드가 시작될 때는 사라져 있다.)

  ______
  ______
  ______
  ______
  X_____
  X_____
  X#____
  X#____

라운드 $2$의 라운드 점수가 $4$이므로, 여기서 $4 \cdot 4 = 16$점을 얻는다. 마지막으로 마지막 벽돌 모양을 $180$도 회전하고 왼쪽에서 두 번째 위치에 떨어뜨리면 다음과 같다:

  ______
  ______
  ______
  ______
  _X____
  _X_X__
  _X_X__
  _X#X__

마지막 라운드의 점수는 $2$이므로 이 라운드에서 $2 \cdot 7 = 14$점을 얻는다. 총 $0 + 16 + 14 = 30$점을 얻었다. 이것이 최적이다.