P15544 [CCC 2026 S5] On the Fence

你最近继承了一块美丽的土地，可以看作一个具有 $N$ 行 $M$ 列的网格。现在你想通过在上面建造一个巨大的围栏来保护你的土地免受闯入者侵扰。你将通过选择至多 $K$ 个网格单元格并用混凝土块填充每个单元格来建造这个围栏；这些单元格就是 **围栏上** 的单元格。由于神秘的建筑法规，位于第 $R$ 行、第 $C$ 列的单元格必须位于围栏上。此外，围栏单元格必须形成一个 **单一连通分量**——你应该能够仅通过围栏单元格垂直或水平（而非对角线）移动，在任意两个围栏单元格之间通行。 第 1 行、第 1 列、第 $N$ 行和第 $M$ 列的单元格被称为 **边缘单元格**。如果一个不在围栏上的单元格可以通过垂直、水平或对角线移动（不穿过任何围栏单元格）到达某个边缘单元格，则该单元格位于围栏 **外部**。否则，该单元格位于围栏 **内部**。下图展示了一些有效和无效围栏的示例。 :::align{center}  ::: 你想尽可能多地保护你的土地。找出你可以在围栏内围住的最大内部单元格数量。

输入的第一行包含一个整数 $T$，表示输入中的测试用例数量。 接下来的 $T$ 行每行包含一个测试用例，由五个空格分隔的整数组成：$N$、$M$、$K$、$R$ 和 $C$（$1 \le K \le NM$，$1 \le R \le N$，$1 \le C \le M$）。

输出 $T$ 行。第 $t$ 行应包含一个整数，即第 $t$ 个测试用例的答案。

#### 样例输入输出解释 以下是两个测试用例的最优围栏，分别围住了 4 个和 3 个内部单元格： :::align{center}  ::: 下表显示了 15 分的分布情况： | 分值 | $T$ 的范围 | $N, M$ 的范围 | 附加约束 | |:-:|:-:|:-:|:-:| | 1 分 | $T \le 1000$ | $1 \le N, M \le 10^9$ | $K = NM$ | | 2 分 | $T \le 10$ | $1 \le N, M \le 6$ | 无 | | 2 分 | $T \le 10$ | $1 \le N, M \le 40$ | 无 | | 2 分 | $T \le 10$ | $1 \le N, M \le 300$ | 无 | | 2 分 | $T \le 10$ | $1 \le N, M \le 2000$ | 无 | | 3 分 | $T \le 10$ | $1 \le N, M \le 10^6$ | 无 | | 3 分 | $T \le 1000$ | $1 \le N, M \le 10^9$ | 无 | 翻译由 DeepSeek 完成