좌표평면에 빨간색 점 N개와 파란색 점 M 개가 있다. 또한, 자연수 W, H가 주어진다.

i번째 (1 ≤ i ≤ N) 빨간색 점의 좌표는 (rx_i, ry_i)이고, j번째 (1 ≤ j ≤ M) 파란색 점의 좌표는 (bx_j, by_j)이다.

모든 점들의 좌표는 서로 다르다.

가로 W, 세로 H인 직사각형을 변이 좌표축에 평행하고 꼭짓점이 정수 좌표에 놓이도록 할 것이다.

이 때 직사각형이 포함하는 빨간색 점과 파란색 점의 개수의 차가 가장 크게 만들고 싶다.

직사각형이 점을 포함한다는 것은, 직사각형의 왼쪽 아래 꼭짓점 좌표가 (a, b)이고

점의 좌표가 (x, y)일 때 a ≤ x ≤ a + W, b ≤ y ≤ b + H를 만족한다는 것이다.

개수의 차의 최댓값을 구하고, 그 답에 해당하는 직사각형의 위치를 찾아라.

아래 예는 평면에 빨간색 점 3개와 파란색 점 4개가 있는 상황을 보여 준다.

원래 각 점에는 크기가 없지만 설명의 편의상 빨간색 점은 동그라미, 파란색 점은 세모로 표시하였다.

W = 5, H = 3으로 주어졌다고 하자.

그 경우 아래와 같이 직사각형의 왼쪽 아래 꼭짓점을 (3, 3)에 놓으면

포함하는 빨간색 점이 1개, 파란색 점이 3개가 되어 개수의 차가 2가 된다.

직사각형을 어디에 놓더라도 개수의 차를 3 이상으로 만들 수는 없기 때문에 답은 2가 된다.

빨강파랑 timer 3s memory 1024MB

빨강파랑 3s 1024MB