SP25236 DEFKIN2 - Defense of a kingdom 2

这是基于问题 DEFKIN（http://www.spoj.com/problems/DEFKIN/）的一个扩展题，建议先解决原题再尝试本题。 Theodore 开发了一款名为“王国防御”的新策略游戏。在游戏的每一关中，玩家都将保卫一个用矩形网格表示的王国。玩家可以在网格的若干单元格中设置弩塔。每座弩塔可以防御其所在行和列的所有单元格。任意两座弩塔不会位于同一行或同一列。 现在，国王给出网格的宽度 $w$，高度 $h$，以及塔的数量 $n$。注意，$n$ 不会超过 $\min(w, h)$。 在网格中放置这些塔有多种方案。 我们定义一个函数 $penalty(N_i)$ 来衡量第 $i$ 种塔放置方案中，最大未被防御的矩形区域的单元格数量。例如，一种放置塔的方案可能会产生一个惩罚值为 12 的未被防御区域。 假设共有 $k$ 种可能的放置方案，那么相应的惩罚值为 $penalty(N_1), penalty(N_2), \ldots, penalty(N_k)$。 玩家的任务是找出所有可能惩罚值中的最小值。

每组测试数据由一行组成，包含三个整数：$w$、$h$ 和 $n$。

针对每组测试数据，输出一个整数，即最小的惩罚值。每个测试数据的结果均输出在新的一行。 **本翻译由 AI 自动生成**