Tea's Birthday Problem 2021

2 secs 1024 MB
tea's icon tea

問題文

てあくんは誕生日ケーキのろうそくの火を消そうとしています。

誕生日ケーキは上から見ると縦の長さ HH 、横の長さ WW の長方形の形をしており、 xyxy 平面上の座標 (0,0)(0, 0)(W,0)(W, 0)(W,H)(W, H)(0,H)(0, H) に頂点が重なるように置かれています。このケーキに NN 本ろうそくが立っており、 ii 番目のろうそくが立っている座標は (xi+0.5,yi+0.5)(x_i+0.5, y_i+0.5) です。

てあくんは 11 回息を吹くごとに、

  • aa の値を決めて直線 x=ax=a 上のすべてのろうそくの火を消す
  • bb の値を決めて直線 y=by=b 上のすべてのろうそくの火を消す

のいずれかを行うことができます。てあくんが誕生日ケーキに立っているすべてのろうそくの火を消すためには最小で何回息を吹く必要があるでしょうか。

制約

  • 1H,W101 \leq H,W \leq 10
  • 1NHW1 \leq N \leq HW
  • 0xiW10 \leq x_i \leq W-1
  • 0yiH10 \leq y_i \leq H-1
  • 入力はすべて整数

入力

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

W H
N
x_1 y_1
:
x_N y_N

出力

答えを出力してください。

サンプル

入力1
3 3
4
0 1
1 0
1 2
2 1
出力2
2
入力2
10 10
29
0 9
1 9
2 9
3 9
4 9
2 8
2 7
2 6
2 5
4 4
5 4
6 4
6 5
5 6
4 6
3 5
3 4
3 3
4 2
5 2
8 3
7 3
6 2
6 1
6 0
7 0
8 2
8 1
9 0
出力2
9

提出


Go (1.21)