1061 - 労働組合

ストーリー

ei1821は筍派(急進派)である。

ゲームをしよう。
縦Hマス、横Wマスの長方形型マップを塗りつぶすだけの簡単なゲームだ。
プレイヤーはN人、Mターン行われる。
N人のプレイヤーは協力して、マス同士が最も多く接触している領域を生成したい。
しかし、ただプレイヤーXとYが塗りつぶしたマスが接触していても一つの領域として結合することは出来ない。
Xが生成したある領域とYが生成したある領域のうちどこか1マスがそれぞれに重複して塗りつぶされていた場合には、その2つの領地は結合しはじめて1つの領域となれる。
最大領地の面積を出力せよ。

入力

1行目に、プレイヤーの人数Nとターン数Mが与えられる。
2行目に、マップの大きさ縦H、横Wが与えられる。
3行目以降、プレイヤーナンバー1からNまで順番に、それぞれが塗りつぶすマップの座標A_iとB_iがN*M回与えられる。

N M
H W
A1-1 B1-1
A1-2 B1-2
...
A1-N B1-N
A2-1 B2-1
...
AM-N BM-N

出力

最大領域の面積を一行で出力せよ。 最後の改行を忘れずに。

制約

• 1 ≤ $N$ ≤ 30
• 1 ≤ $M$ ≤ 5000
• 2 ≤ $H$ , $W$ ≤ 1000
• 1 ≤ $A$_i ≤ $H$
• 1 ≤ $B$_i ≤ $W$

入出力例

例1

入力

3 3
3 3
1 1
1 1
1 1
1 2
1 3
1 2
2 2
2 1
2 3

出力

4

3人のプレイヤーが、1番から順番にマスを塗るのを3回繰り返すため、1ターン目は全員が(1,1)のマスを塗ったことになる。
隣接している(1,2)はプレイヤー1が、(2,1)はプレイヤー2が3ターン目に塗ったため領域は広がる。
3ターン目にプレイヤー1が(2,2)を塗ると、隣接した(1,2)をプレイヤー1がすでに塗っているため領域はさらに広がる。
プレイヤー1とプレイヤー2それぞれが持つ領域に重複部分が存在するため領域は結合され、最終的に最も広い領域面積は4となる。

例2

入力

3 3
3 3
1 1
1 1
1 1
1 2
2 2
2 1
3 1
1 3
3 3

出力

3

例3

入力

16 2
4 4
1 1
2 1
3 1
4 1
4 2
4 3
4 4
3 4
3 3
3 2
2 2
2 3
2 4
1 4
1 3
1 2
2 1
3 1
4 1
4 2
4 3
4 4
3 4
3 3
3 2
2 2
2 3
2 4
1 4
1 3
1 2
1 1

出力

16

全てのマスで誰かと誰かが重複している。