시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 381 134 43 21.182%

문제

DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태로 이루어져 있다. 각 격자는 정사각형 모양이며, 퍼즐 조각이 있을 수도 있고, 없을 수도 있다. 즉, 아래 그림도 올바른 퍼즐의 완성 형태이다.

성공적으로 DIY가 끝나서 퍼즐이 2개가 완성되었는데, 보관해야 하는 액자를 아직 구매하지 않았다. 그 이유는, 호석이는 엄청난 짠돌이기 때문에 퍼즐 하나마다 액자 하나를 사는 것은 상상도 못하기 때문이다. 액자의 가격은 액자의 넓이(행의 개수 × 열의 개수) 로 결정된다. 즉, 퍼즐 두 개를 퍼즐 조각끼리 같은 격자에서 만나지 않도록 배치해서 하나의 액자에 담는 방법 중에 가장 적은 비용일 때를 찾아보자! 단, 각 퍼즐은 90도, 180도, 270도로 자유롭게 회전시켜도 된다.

입력

첫 줄에 퍼즐의 크기를 나타내는 N1, M1이 공백으로 구분되어 주어진다. 이어서 N1개의 줄에 걸쳐서 완성된 첫 번째 퍼즐의 정보가 주어진다. 각 행마다 M1개의 0 또는 1이 공백없이 주어진다. 다음 줄에 퍼즐의 크기를 나타내는 N2, M2이 공백으로 구분되어 주어진다. 이어서 N2개의 줄에 걸쳐서 완성된 두 번째 퍼즐의 정보가 주어진다. 각 행마다 M2개의 0 또는 1이 공백없이 주어진다. 0이 써있는 격자는 퍼즐 조각이 없는 격자이며 1은 있는 격자이다. 두 퍼즐 모두 4개 모서리에 최소 하나의 1은 존재하는 것이 보장된다.

출력

두 개의 퍼즐을 담을 수 있는 액자들 중에 최소 넓이를 출력한다.

제한

  • 1 ≤ N1, M1, N2, M2 ≤ 50

예제 입력 1

5 5
11111
10000
11111
10000
11111
5 3
101
101
101
101
111

예제 출력 1

30

2번 블록을 반시계 방향으로 90도 회전시 뒤에 합치면

111110
122222
111112
122222
111110

으로 합쳐진다. 여기서 1은 첫 번째 퍼즐의 조각, 2는 두 번째 퍼즐의 조각, 0은 빈 칸이다. 이것보다 작은 넓이는 없다.

 

예제 입력 2

4 4
1001
0100
1011
1110
4 4
1000
0010
1101
0110

예제 출력 2

16

채점 및 기타 정보

  • 19개 이상의 데이터를 맞아야 를 받는다.