Clear The Matrix

4개의 행과 n개의 열로 이루어진 행렬 f가 주어진다. 행렬의 각 원소는 별표(*) 또는 점(.)이다.

다음 연산을 임의의 횟수만큼 수행할 수 있다. f에서 크기가 k × k (where 1 ≤ k ≤ 4)인 정사각 부분 행렬을 선택하고, 선택한 부분 행렬의 각 원소를 점으로 바꾼다. 크기가 k × k인 부분 행렬을 선택하는 데에는 ak개의 동전이 든다.

모든 별표를 점으로 바꾸기 위해 지불해야 하는 동전의 최소 개수는 얼마인가?

첫째 줄에 f의 열 개수를 나타내는 정수 n (4 ≤ n ≤ 1000)이 주어진다.

둘째 줄에 1 × 1, 2 × 2, 3 × 3, 4 × 4 크기의 정사각 부분 행렬을 바꾸는 비용을 각각 나타내는 4개의 정수 a1, a2, a3, a4 (1 ≤ ai ≤ 1000)이 주어진다.

이어서 네 줄이 주어지며, 각 줄에는 n개의 문자가 주어져 행렬 f의 한 행을 나타낸다. 각 문자는 점 또는 별표이다.

모든 별표를 점으로 바꾸는 데 필요한 동전의 최소 개수를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 8개의 동전을 사용하여 왼쪽 위 모서리의 3 × 3 부분 행렬을 바꾸고, 1개의 동전을 사용하여 오른쪽 아래 모서리의 1 × 1 부분 행렬을 바꿀 수 있다.

두 번째 예제에서 최선의 방법은 2 – 5열을 포함하는 4 × 4 부분 행렬과 2 – 3행 및 6 – 7열로 이루어진 2 × 2 부분 행렬을 바꾸는 것이다.

세 번째 예제에서는 왼쪽 위 모서리의 3 × 3 부분 행렬을 선택한 다음, 2 – 4행과 2 – 4열로 이루어진 3 × 3 부분 행렬을 선택할 수 있다.