스트라이크 존

야구의 스트라이크 존은 타자가 스윙하지 않았을 때 투구가 그 안을 통과하면 스트라이크로 선언되는 공간의 부피이다. 스트라이크 존을 벗어난 투구는 타자가 스윙하지 않았을 때 볼이라고 한다. 그림 H.1은 야구 경기 중 공 추적 장치가 기록한 투구의 위치를 보여준다. 파란 점은 스트라이크, 빨간 점은 볼로 선언된 투구이다. 이는 이러한 공 추적 데이터를 분석해서 그 경기의 스트라이크 존을 나타내는 직사각형 영역을 정의하려는 동기가 된다.

그림 H.1: 야구 경기 중 투구의 위치. 파란 점은 스트라이크, 빨간 점은 볼로 선언된 투구이다.

이 문제에서는 평면 위의 두 점 집합 P1, P2와 두 양의 상수 c1, c2가 주어진다. 평가 함수 eval(R) = c1 × s - c2 × b를 최대화하는 축에 평행한 직사각형 R을 찾아야 한다. 여기서 s는 P1 ∩ R에 속하는 점의 개수이고 b는 P2 ∩ R에 속하는 점의 개수이다.

프로그램은 표준 입력에서 입력을 읽는다. 입력의 첫 줄에는 정수 n1 (1 ≤ n1 ≤ 1,000)이 주어지며, n1은 P1에 속하는 점의 개수이다. 다음 n1개 줄에는 각각 두 정수가 주어지며, -109부터 109까지의 범위로 P1에 속하는 점의 좌표를 나타낸다. 다음 줄에는 정수 n2 (1 ≤ n2 ≤ 1,000)가 주어지며, n2는 P2에 속하는 점의 개수이다. 다음 n2개 줄에는 각각 두 정수가 주어지며, -109부터 109까지의 범위로 P2에 속하는 점의 좌표를 나타낸다. P1 ∪ P2에서 x 좌표나 y 좌표가 같은 두 점은 존재하지 않는다. 다음 줄에는 두 정수 c1과 c2가 주어지며, 1부터 10,000까지의 범위이다.

프로그램은 표준 출력에 출력을 쓴다. P1과 P2에 대해 c1과 c2에 따른 eval 값이 최대가 되는 축에 평행한 직사각형 R에 대해, eval(R)을 나타내는 정수 하나를 한 줄에 정확히 출력한다.