Dragon(ドラゴン) - joi2011-day1

時間制限: 10秒

メモリ制限: 64MB

IOI の競技会場にドラゴンたちが入ってきてしまった．競技会場は長方形の部屋であり，H 行 W 列のマスに区切られている．行には 1 から H まで，列には 1 から W までの番号がふられていて，x 行目 y 列目のマスを (x，y) で表す．入ってきたドラゴンは N 匹であり，i 匹目のドラゴンは (X_i，Y_i) にいる．同じマスにドラゴンが 2匹以上いることはない．ドラゴンと同じ行または同じ列のマスには，ドラゴンが炎を吹いて攻撃することがある．選手は，ドラゴンのいないマスに， 1 マスに 1 人まで入ることができるが，ドラゴンに攻撃される可能性のあるマスには入ることができない．JOI の M 理事長は，少しでも参加可能な選手の数を増やすため，防火装置をもってドラゴンのいないどこかのマスに立つことにした．選手とドラゴンが同じ行または列にいる場合でも，間に M 理事長がいれば炎を通さないので，選手はそのドラゴンからは攻撃されない．ただし， M 理事長は全ての問題の答えを知っているので， M 理事長のいるマスには選手は入れない．

課題

競技会場の大きさの情報と，ドラゴンの位置の情報が与えられたとき，M 理事長が最適なマスに立った場合の競技会場に入れる選手の人数の最大値を求めるプログラムを作成せよ．

制限

`1 \leq H \leq 1\,000\,000\,000`	競技会場の行数
`1 \leq W \leq 1\,000\,000\,000`	競技会場の列数
`1 \leq N \leq 100\,000`	ドラゴンの数
`1 \leq X_i \leq H，1 \leq Y_i \leq W`	`i` 番目のドラゴンの位置

入力

標準入力から以下の入力を読み込め．

1 行目には整数 H，W，N が空白を区切りとして書かれている．
続く N 行にはドラゴンの位置の情報が書かれている．i + 1 行目(1 \leq i \leq N) には，i 番目のドラゴンの位置を表す整数 X_i，Y_i が空白を区切りとして書かれている．ただし，同じマスにドラゴンが2匹以上いることはない．また，少なくとも 1 つドラゴンのいないマスがある．

出力

標準出力に，競技会場に入れる選手の人数の最大値を 1 行で出力せよ．

採点基準

採点用データのうち，配点の 30% 分については，H \leq 1\,000 かつ W \leq 1\,000 を満たす．
採点用データのうち，配点の 40% 分については，N \leq 1\,000 を満たす．
採点用データのうち，配点の 20% 分については，これら 2 つの条件の両方を満たす．
採点用データのうち，配点の 50% 分については，これら 2 つの条件の少なくとも一方を満たす．

入出力の例

入力例	出力例
`4 6 3 2 4 3 5 2 3`	`9`

下図は，この入力例に対応している．D はドラゴンを表す．

下図は，M 理事長と選手の配置例であり，M は M 理事長を，C は選手を表す．この配置では 9 人の選手が入ることができ，M 理事長をどこに配置しても 10 人以上の選手が入ることはできない．