직사각형 스탬프
시간 제한2초메모리 제한512 MB
크기가 최대 4x4인 직사각형 스탬프 16개 이하가 주어질 때, 나중에 찍은 색이 이전 색을 완전히 덮는 규칙 아래에서 4x4 목표 그림을 완성하는 최소 횟수를 구한다.
문제
ICPC에서 좋은 성적을 내려면 수련이 필요하다. 토끼는 ICPC에서 이기고 싶어서 오늘도 수련을 하기로 했다.
오늘의 수련은 그림을 그리면서 창의력을 기르는 것이다. 네모난 스탬프를 사용해 무늬를 잘 그려 보자.
크고 작은 여러 스탬프를 사용해 4 × 4 격자 종이에 지정된 대로 빨강, 초록, 파랑 그림을 완성하고 싶다. 스탬프는 직사각형이며 격자에 딱 맞춰 사용한다. 스탬프의 세로와 가로를 바꿀 수는 없다.
종이는 처음에 아무 색도 칠해지지 않은 상태이다. 종이에 스탬프를 누르면 눌린 부분이 스탬프의 색으로 바뀌고, 아래에 가려진 색은 전혀 보이지 않는다. 스탬프의 색은 묻히는 잉크로 정해지므로 어떤 스탬프든 원하는 색을 고를 수 있다. 스탬프는 종이에서 일부가 삐져나간 상태로 눌러도 되며, 삐져나간 부분은 무시된다.
한 스탬프를 여러 번 사용할 수 있다. 같은 스탬프를 다른 색에 사용해도 된다. 스탬프를 누르는 일은 다소 신경이 쓰이므로, 스탬프를 누르는 횟수를 최대한 줄이고 싶다.
입력
N
H1 W1
...
HN WN
C1,1C1,2C1,3C1,4
C2,1C2,2C2,3C2,4
C3,1C3,2C3,3C3,4
C4,1C4,2C4,3C4,4
N은 스탬프의 개수, H**i, W**i (1 ≤ i ≤ N)는 각각 i번째 스탬프의 세로 길이, 가로 길이를 나타내는 정수이다. C**i, j (1 ≤ i ≤ 4, 1 ≤ j ≤ 4)는 위에서 i번째 행, 왼쪽에서 j번째 열의 칸에 지정된 그림의 색을 나타내는 문자이다. 빨강은 R, 초록은 G, 파랑은 B로 나타낸다.
1 ≤ N ≤ 16, 1 ≤ H**i ≤ 4, 1 ≤ W**i ≤ 4를 만족한다. (H**i, W**i)로 같은 조합은 여러 번 나타나지 않는다.
출력
그림을 완성하기 위해 스탬프를 눌러야 하는 최소 횟수를 한 줄에 출력하라.