바닥 벽돌 채우기

로버트는 새 방의 바닥을, 여러 가지 색깔에 기묘한 모양을 가진 벽돌로 만든 무늬로 꾸몄다. 작업을 끝내고 나서 그는 한 가지 문제를 발견했다. 무늬의 바깥 경계가 완전한 직사각형이 아니어서 바닥의 일부가 아직 비어 있었던 것이다. 벽돌들의 모양이 워낙 특이해서, 남은 빈 부분을 빈틈없이 채우는 일은 결코 쉽지 않다. (크기가 한 칸짜리인 벽돌도 있기는 하지만, 이런 벽돌은 보통 매우 비싸다. 그림 1은 벽돌 집합의 예를 보여 준다.)

로버트는 자신이 만든 무늬가 무척 자랑스러워서 벽돌 하나도 옮기려 하지 않는다. 대신 그는, 주어진 벽돌들을 사용해 남은 빈 바닥을 완전히 채우되 벽돌을 사는 데 드는 Gil이 최소가 되도록 하는 방법을 찾아 달라고 부탁한다. 벽돌은 서로 겹칠 수 없고, 빈 칸은 모두 덮여야 하며, 어떤 벽돌도 빈 영역 밖으로 삐져나올 수 없다. 벽돌은 회전할 수는 있지만 뒤집을 수는 없다. 또한 모든 벽돌은 $3 \times 3$ 상자 안에 들어간다고 가정해도 좋다.

그림 1

무늬가 바닥의 대부분을 덮고 있기 때문에, 덮이지 않은 부분은 실제로는 직사각형 바닥의 아래쪽 경계에 위치한다. 따라서 빈 영역은, 왼쪽에서부터 각 열에서 비어 있는 칸의 개수를 나타내는 정수들의 수열로 나타낼 수 있다. 예를 들어 그림 2의 모양은 11개의 정수 2 2 1 2 3 5 2 3 3 4 1로 나타낼 수 있다. 이 정수들은 모두 $5$ 이하이다. 그림 3은 그림 1의 벽돌 집합으로 바닥을 최소 비용으로 채우는 한 가지 방법을 보여 준다.

그림 2

그림 3

입력은 최대 $20$개의 테스트 케이스로 이루어진다.

각 테스트 케이스는 다음과 같이 주어진다.

• 첫째 줄에 바닥의 너비를 나타내는 정수 $n$ ($1 \le n \le 1000$)이 주어진다.
• 둘째 줄에 공백 하나로 구분된 $n$개의 정수가 주어진다. 이 정수들은 위에서 설명한 대로 빈 영역을 나타내며, 왼쪽에서부터 각 열에서 비어 있는 칸의 개수이다. 각 값은 $5$ 이하이다.
• 셋째 줄에 사용할 수 있는 벽돌 종류의 수를 나타내는 정수 $m$ ($1 \le m \le 100$)이 주어진다.
• 이어서 $m$개의 벽돌에 대한 설명이 주어진다. 각 벽돌은 네 줄로 주어진다. 첫째 줄은 그 벽돌의 가격(Gil)을 나타내는 양의 정수이다. 이어지는 세 줄은 각각 세 개의 문자로 벽돌의 모양을 나타내며, 점(.)은 빈 공간을, 우물 정 기호(#)는 한 칸짜리 블록을 뜻한다. 한 벽돌을 이루는 블록들은 항상 서로 연결되어 있다. 각 벽돌 종류는 몇 번이든 사용할 수 있다.

마지막 테스트 케이스 다음에는 0 하나만 있는 줄이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄에 Need at least g Gil(s).를 출력한다. 여기서 $g$는 주어진 벽돌로 빈 바닥을 채우는 데 필요한 최소 Gil의 수이다. 바닥을 채울 수 없다면 대신 Impossible.을 출력한다. 테스트 케이스 사이에는 빈 줄을 출력하지 않는다.