P11168 「CMOI R1」First Town of This Journey／Grid Covering
题目背景
$\small\color{white}/10^{\text{th}}\text{Problem by AtC}.$
本题中认为两个点间的连线为以这两个点作为端点的线段。
题目描述
$\text{BiOI}$ 有一个 $n$ 行 $m$ 列的网格。你需要选出最少的格点，使得任意两个**不同的**格点的连线至少经过一个被选中的点（这里我们认为一条线段**经过了**它的两个端点）。
$\text{CmOI}$ 觉得这个问题太简单了，所以他会另外给定 $a,b,x$，表示第 $a$ 行第 $b$ 列的格点必须被或不被选中：
* $x=0$ 时该格点不可选中；
* $x=1$ 时该格点必须选中。
你只需要求出最少选出几个格点，$\text{BiOI}$ 和 $\text{CmOI}$ 会把网格和你的答案一起丢给 $\text{ArCu}$ 让他构造方案。
输入格式
无
输出格式
无
说明/提示
$\text{Details about Subtasks}:$
所有数据满足 $1\leq n,m