004 - Two-dimensional imos method

問題

高さH、幅がWの長方形がある。
その中のx_i,y_iの位置から下にh_i、右にw_iの大きさの長方形を作っていく。

入力

H W
N
x1 y1 w1 h1 
x2 y2 w2 h2
.
.
.
xN yN wN hN

出力

重なっている長方形の個数が最も多い部分の、重なっている長方形の個数を出力する。

制約

• 1 ≦ H,W ≦ 1000
• 0 ≦ N ≦ 100000
• 0 ≦ y_i < H
• 0 ≦ x_i < W
• 1 ≦ h_i ≦　H - y_i
• 1 ≦ w_i ≦ W - x_i

長方形の左上の座標を0,0とする。

入力例

5 5
3
0 0 2 2
0 0 3 3
0 0 5 5

出力例

3

解説

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

全ての操作を終えた後の四角形の中身は上の様になる。
よって3を出力する。

入力例２

5 5
3
1 1 2 2
0 0 3 3
3 3 1 1

出力例２

2