종이 겹치기
시간 제한2초메모리 제한128 MB
회전과 반전이 가능한 두 종이를 자유롭게 겹쳐 놓았을 때 만들어지는 격자에서 X로만 이루어진 가장 큰 직사각형의 넓이를 구합니다.
문제
세준이는 두 장의 격자 종이를 가지고 있다. 첫 번째 종이의 크기는 N1 x M1이고, 두 번째 종이의 크기는 N2 x M2이다. 각 칸은 빈칸 . 또는 채워진 칸 X로 표시된다.
두 종이는 서로 겹쳐 놓을 수 있고, 전혀 겹치지 않게 놓을 수도 있다. 각 종이는 놓기 전에 90도 단위로 회전하거나 뒤집을 수 있다. 두 종이를 배치한 뒤, 적어도 한 종이에서 X인 칸은 채워진 칸으로 본다.
가능한 배치 중 X로만 이루어진 직사각형의 최대 넓이를 구하시오.
입력
첫째 줄에 첫 번째 종이의 크기 N1과 M1이 주어진다. 다음 N1개의 줄에는 첫 번째 종이의 정보가 주어진다.
그다음 줄에 두 번째 종이의 크기 N2와 M2가 주어진다. 다음 N2개의 줄에는 두 번째 종이의 정보가 주어진다.
출력
첫째 줄에 X로만 이루어진 가장 큰 직사각형의 넓이를 출력한다.
제한
- 1 <= N1, M1, N2, M2 <= 5
- 각 종이의 모든 칸은
.또는X이다.