说明

芭芭拉有一座花园。花园可以表示为一个 $n \times m$ 的网格。她在花园里放置了 $k$ 块石板，以便每天都能从一块石板跳到另一块石板上享受乐趣。这些石板编号为 $1$ 到 $k$。每块石板完全占据网格中的一个单元格，且没有两块石板被放在同一个单元格中。

然而，一个邪恶的人，小芭拉，将放置一个特殊的装置，该装置会占据花园中的一个矩形区域。如果有任何石板与该装置重叠，它就会爆炸并摧毁整个花园！

为了避免爆炸，芭芭拉希望在花园内移动石板来重新布置它们。在 石板移动过程中，石板之间必须保持不重叠。消耗的能量等于所有被移动过的石板中最大的编号。现在芭芭拉想知道重新布置石板所需的最小能量，以便她能将能量节省下来用于“其他目的”。

例如，假设装置将被放置在蓝色矩形中。那么芭芭拉可以如下重新布置石板。请注意，在整个过程中石板都不重叠，而不仅仅是在重新布置之后。所有被移动过的石板的编号都不超过 $4$，因此消耗的能量为 $4$。

:::align{center} :::

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$。

接下来 $k$ 行，其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 块石板位于第 $x_i$ 行的第 $y_i$ 个单元格。

最后一行包含四个整数 $u_1$、$v_1$、$u_2$ 和 $v_2$，表示装置的左上角位于第 $u_1$ 行的第 $v_1$ 个单元格，右下角位于第 $u_2$ 行的第 $v_2$ 个单元格。

输出格式

输出重新布置石板所需的最小能量。如果没有石板需要移动，消耗的能量为 $0$。如果爆炸无法避免，则输出 $-1$。

3 5 8
1 4
1 5
2 3
2 2
3 3
3 4
2 5
1 2
1 3 1 5

4

3 3 1
2 2
1 1 3 3

-1

提示

• $1 \le n \le 500$
• $1 \le m \le 500$
• $1 \le k \le n \times m$
• $1 \le x_i \le n$
• $1 \le y_i \le m$
• $1 \le u_1 \le u_2 \le n$
• $1 \le v_1 \le v_2 \le m$
• 所有 $(x_i, y_i)$ 对互不相同。

翻译由 DeepSeek V3.2 完成