하야시는 18 세기에 아이주지방에 있는 니시칸사무라이 학교의 선생님이었다. 아이주 지방의 성주는 그의 교육적 업적에 대한 포상으로 직사각형 모양의 땅을 하사하기로 하였다. 성주는 땅의 가로 ,세로 길이를 알려 준후 어떤 땅을 선택할 것인가는 그가 결정하도록 하였다.
사각형의 토지 내에는 일본사과 페르시몬이라 불리는 일본 사과가 심겨져 있다.
페르시몬 사과를 좋아하는 하야시는 주어진 크기에서 가장 많은 페르시몬 트리를 얻고자 한다.
예를 들어, 그림 1 에서는 전체 크기가 폭 이 10 이고 높이가 8 인 사각형 토지 정보가 주어진다.
* 표는 페르시몬 트리가 심겨져 있는 위치이다.
만약 폭과 높이가 4 와 3 이라면 실선으로 둘러싸인 지역이 가장 많은 페르시몬 나무를 포함한다. 비슷하게 , 폭과 높이가 6 과 4 라면 점선으로 연결된 지역이 가장 많은 나무를 포함한다.
높이와 폭을 바꿀수는 없다. 4 와 3 과 3 과 4 는 다르다.
해야 할 일은 폭과 높이가 주어질 때 가장 많은 페르시몬 트리를 포함하는 지역을 찾아 최대 사과의 개수를 출력하는 것이다.
N W H x1 y1 x2 y2 ... xN yN S TN 은 페르시몬 트리의 수이고 , 500 보다 크지 않다. W 는 폭 , H 는 높이이다. W 와 H 는 100 보다 작은 양의 정수이다. 다음으로 N 개의 페르시몬 트리의 좌표가 xi , yi 로 주어진다. 1 <= xi <= W , 1 <= yi <= H 이고 같은 지점에 두개의 트리를 가지지 않는다. 입력으로 그들의 위치가 정렬되어서 입력되지는 않는다. 마지막 S 와 T 는 성주가 하사한 땅의 폭과 높이이다. 1 <= S <= W , 1 <= T <= H 입력의 끝은 0 이다.
입력 16 10 8 2 2 2 5 2 7 3 3 3 8 4 2 4 5 4 8 6 4 6 7 7 5 7 8 8 1 8 4 9 6 10 3 4 3 8 6 4 1 2 2 1 2 4 3 4 4 2 5 3 6 1 6 2 3 2 0 출력 4 3
출처:Japan 2003 Domestic