#P2029. Get Many Persimmon Trees

Get Many Persimmon Trees

题目描述

在18世纪,林清司(Seiji Hayashi)长期担任会津藩日新馆武士学校的教授。为表彰他在教育上的功绩,会津藩主松平容颂(Katanobu Matsudaira)决定赐予他一块位于会津盆地大田野中的矩形庄园。庄园的**宽度WW和高度HH**由藩主严格指定,但林教授可以自由选择庄园的位置。

田野中种植了许多日本柿子树(会津特产"无籽柿")。由于林教授特别喜爱柿子,他希望在自己的庄园内尽可能多地包含柿子树

示例(图1):

  • 整个田野是10×810 \times 8的矩形网格,每个*代表一棵柿子树。
    • 若庄园尺寸为4×34 \times 3(实线区域),最多包含66棵树。
    • 若为6×46 \times 4(虚线区域),最多1212棵。
    • 若为3×43 \times 4(点线区域),最多55棵。
  • 注意:庄园的宽度和高度不可交换4×34 \times 33×43 \times 4视为不同尺寸)。

输入格式

  • 每个测试用例格式如下:
    N
    W H
    x1 y1
    x2 y2
    ...
    xN yN
    S T
    
    • NN:柿子树数量(1N<5001 \leq N < 500)。
    • W,HW, H:田野的宽度和高度(1W,H<1001 \leq W, H < 100)。
    • xi,yix_i, y_i:第ii棵树的坐标(原点为111xiW1 \leq x_i \leq W1yiH1 \leq y_i \leq H,且所有坐标唯一)。
    • S,TS, T:庄园的指定宽度和高度(1SW1 \leq S \leq W1TH1 \leq T \leq H)。
  • 输入以单独一行的00结束。

输出格式

对每个测试用例,输出一行:庄园内最多可包含的柿子树数量

样例输入

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