蒙格性质

题目描述

有一个 $H$ 行 $W$ 列的网格，每个格子中写着一个整数。 从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子中写着的整数为 $A_{i, j}$。

判断该网格是否满足下面的条件：

对于所有满足 $1 \le i_1 \lt i_2 \le H$ 且 $1 \le j_1 \lt j_2 \le W$ 的整数四元组 $(i_1, i_2, j_1, j_2)$，都有

$$A_{i_1, j_1} + A_{i_2, j_2} \le A_{i_2, j_1} + A_{i_1, j_2}$$

成立。

输入格式

输入按以下格式从标准输入给出：

$H$ $W$
$A_{1, 1}$ $A_{1, 2}$ $\cdots$ $A_{1, W}$
$A_{2, 1}$ $A_{2, 2}$ $\cdots$ $A_{2, W}$
$\vdots$
$A_{H, 1}$ $A_{H, 2}$ $\cdots$ $A_{H, W}$

输出格式

如果网格满足题目描述中的条件，则输出 Yes；否则输出 No。

样例

3 3
2 1 4
3 1 3
6 4 1

Yes

满足 $1 \le i_1 \lt i_2 \le H$ 且 $1 \le j_1 \lt j_2 \le W$ 的整数四元组 $(i_1, i_2, j_1, j_2)$ 共有九组，对它们全部有 $A_{i_1, j_1} + A_{i_2, j_2} \le A_{i_2, j_1} + A_{i_1, j_2}$ 成立。下面举几个例子。

例如 $(i_1, i_2, j_1, j_2) = (1, 2, 1, 2)$ 时，有 $A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \le 3 + 1 = A_{i_2, j_1} + A_{i_1, j_2}$。

例如 $(i_1, i_2, j_1, j_2) = (1, 2, 1, 3)$ 时，有 $A_{i_1, j_1} + A_{i_2, j_2} = 2 + 3 \le 3 + 4 = A_{i_2, j_1} + A_{i_1, j_2}$。

例如 $(i_1, i_2, j_1, j_2) = (1, 2, 2, 3)$ 时，有 $A_{i_1, j_1} + A_{i_2, j_2} = 1 + 3 \le 1 + 4 = A_{i_2, j_1} + A_{i_1, j_2}$。

例如 $(i_1, i_2, j_1, j_2) = (1, 3, 1, 2)$ 时，有 $A_{i_1, j_1} + A_{i_2, j_2} = 2 + 4 \le 6 + 1 = A_{i_2, j_1} + A_{i_1, j_2}$。

例如 $(i_1, i_2, j_1, j_2) = (1, 3, 1, 3)$ 时，有 $A_{i_1, j_1} + A_{i_2, j_2} = 2 + 1 \le 6 + 4 = A_{i_2, j_1} + A_{i_1, j_2}$。

对于其余的四元组 $(i_1, i_2, j_1, j_2) = (1, 3, 2, 3), (2, 3, 1, 2), (2, 3, 1, 3), (2, 3, 2, 3)$，也可以同样验证性质成立。

因此，应输出 Yes。

2 4
4 3 2 1
5 6 7 8

No

因为条件不满足，所以应输出 No。

这是因为，例如 $(i_1, i_2, j_1, j_2) = (1, 2, 1, 4)$ 时，有 $A_{i_1, j_1} + A_{i_2, j_2} = 4 + 8 \gt 5 + 1 = A_{i_2, j_1} + A_{i_1, j_2}$。

数据范围

• 输入均为整数。
• $2 \le H, W \le 50$
• $1 \le A_{i, j} \le 10^9$