종이 겹치기

시간 제한2초메모리 제한128 MB

문제

세준이는 두 장의 격자 종이를 가지고 있다. 첫 번째 종이의 크기는 N1 x M1이고, 두 번째 종이의 크기는 N2 x M2이다. 각 칸은 빈칸 . 또는 채워진 칸 X로 표시된다.

두 종이는 서로 겹쳐 놓을 수 있고, 전혀 겹치지 않게 놓을 수도 있다. 각 종이는 놓기 전에 90도 단위로 회전하거나 뒤집을 수 있다. 두 종이를 배치한 뒤, 적어도 한 종이에서 X인 칸은 채워진 칸으로 본다.

가능한 배치 중 X로만 이루어진 직사각형의 최대 넓이를 구하시오.

입력

첫째 줄에 첫 번째 종이의 크기 N1과 M1이 주어진다. 다음 N1개의 줄에는 첫 번째 종이의 정보가 주어진다.

그다음 줄에 두 번째 종이의 크기 N2와 M2가 주어진다. 다음 N2개의 줄에는 두 번째 종이의 정보가 주어진다.

출력

첫째 줄에 X로만 이루어진 가장 큰 직사각형의 넓이를 출력한다.

제한

  • 1 <= N1, M1, N2, M2 <= 5
  • 각 종이의 모든 칸은 . 또는 X이다.