問題

HH マス、横 WW マスのグリッドがあり、上から pp 番目、左から qq 番目のマスをマス (p,q)(p, q) と書きます。
NN 個のマスは黒色に塗られており、それぞれマス (pi,qi)(p_i, q_i) (1iN)(1 \leq i \leq N)です。それ以外のマスは白色に塗られています。

あなたは以下の操作を好きな回数( 00 回でも良い)行うことができます。

  • 11 以上 H1H-1 以下の整数 xx と、 11 以上 W1W-1 以下の整数 yy を好きに選ぶ。
  • マス (x,y),(x, y), マス (x+1,y),(x+1, y), マス (x,y+1),(x, y+1), マス (x+1,y+1)(x+1, y+1) について、色の反転を行う。

色の反転とは、そのマスが黒色で塗られていた場合は白色に、白色で塗られていた場合は黒色に塗り替えることを指します。

あなたの目標は、グリッドの全てのマスを白色にすることです。
目標の達成に必要な最小の操作回数を求めてください。不可能ならば -1 を出力してください。

制約

  • 0N2×1050 \leq N \leq 2 \times 10^5
  • 2H,W2×1052 \leq H, W \leq 2 \times 10^5
  • 1piH1 \leq p_i \leq H
  • 1qiW1 \leq q_i \leq W
  • ij(pi,qi)(pj,qj)i \ne j \Longrightarrow (p_i, q_i) \ne (p_j, q_j)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

NNHHWW
p1p_1q1q_1
\vdots
pNp_NqNq_N

出力

答えを出力せよ。

サンプル 1

入力1
4 3 2
1 1
1 2
3 1
3 2
出力1
2

グリッドは始めこのようになっています。ここで、 # は黒色に塗られているマス、 . は白色に塗られているマスとします。

##
..
##

以下の操作で目標を達成できます。

  • x=2,y=1x = 2, y = 1 を選ぶ。グリッドは次のように変わる。
##
##
..
  • x=1,y=1x = 1, y = 1 を選ぶ。グリッドは次のように変わる。
..
..
..

これで目標を達成できました。これが最小の操作回数となるため、 22 を出力します。

サンプル 2

入力2
3 5 5
2 4
5 3
2 3
出力2
-1

このグリッドで全てのマスを白色にすることは不可能です。

サンプル 3

入力3
12 60 48
52 19
59 45
34 19
1 45
52 36
59 22
8 19
1 19
34 45
8 36
52 22
52 45
出力3
883

Submit


Go (1.21)