P15401 [NOISG 2026 Prelim] Airplane 2（暂无数据）

在 NOI 2023 之后，猴子潘从兔子本森手中接管了一架飞机的控制权。飞机上的乘客座位排列成 $h$ 行 $w$ 列。行从上到下编号为 $1$ 到 $h$，列从左到右编号为 $1$ 到 $w$。我们将位于第 $i$ 行第 $j$ 列的座位记为 $(i, j)$。 CEO 潘向 $k$ 名乘客出售机票，乘客编号从 $1$ 到 $k$。第 $i$ 名乘客有一个偏好列 $c[i]$，但潘可以为他们分配任意行 $r[i]$。不能有两名乘客占据同一个座位。 为了保持飞机上的重量均匀分布，坐在较前行中的乘客不得坐在较后列中。形式化地说，对于任意两个已分配的座位 $(a_1, b_1)$ 和 $(a_2, b_2)$，如果 $a_1 < a_2$，则 $b_1 \le b_2$。 CEO 潘将 **乘客总满意度** 定义为所有已分配座位对之间的 **最小** 曼哈顿距离。一对座位 $(a_1, b_1)$ 和 $(a_2, b_2)$ 之间的曼哈顿距离为 $|a_1 - a_2| + |b_1 - b_2|$，其中 $|x|$ 表示 $x$ 的绝对值。 帮助潘确定在所有有效的行分配中可能得到的 **最大** 乘客总满意度，或者确定不存在有效的行分配。

你的程序必须从标准输入中读取数据。 输入的第一行包含三个以空格分隔的整数 $h$、$w$ 和 $k$。 输入的第二行包含 $k$ 个以空格分隔的整数 $c[1], c[2], \ldots, c[k]$。

你的程序必须输出到标准输出。 输出一个整数，即最大乘客总满意度。如果没有有效的行分配，则输出 $-1$。

#### 样例测试用例 1 解释 飞机有 $h = 5$ 行和 $w = 1$ 列。机上共有 $5 \times 1 = 5$ 个座位。因此，潘不可能为 $k = 6$ 名乘客分配互不相同的座位。 #### 样例测试用例 5 解释 :::align{center}  ::: 上图展示了一种能够最大化 **乘客总满意度** 的有效行分配方案。每个打叉的格子表示该座位被分配给了一名乘客。第一名乘客被分配到第 1 行，其余乘客被分配到第 4 行。 乘客 2（座位 $(4, 1)$）和乘客 5（座位 $(4, 3)$）之间的曼哈顿距离为 $|4 - 4| + |1 - 3| = 2$，这是所有乘客对中的最小值。因此，此分配的 **乘客总满意度** 为 2。 下图展示了一个 **无效** 行分配的示例。 :::align{center}  ::: 尽管此分配中的 **乘客总满意度** 为 3，但乘客 3（座位 $(1, 11)$）和乘客 4（座位 $(3, 7)$）会导致重量分布不均匀，因为乘客 3 坐在比乘客 4 更前的行但更后的列。 #### 子任务 对于所有测试用例，输入均满足以下范围： - $1 \le h, w \le 10^9$ - $2 \le k \le 200\,000$ - 对于所有 $1 \le i \le k$，$1 \le c[i] \le w$ 你的程序将在满足以下限制的输入实例上进行测试： | 子任务 | 分值 | 附加约束 | |:------:|:----:|:--------:| | 0 | 0 | 样例测试用例 | | 1 | 5 | $w = 1$ | | 2 | 5 | 对于所有 $1 \le i \le k$，有 $c[i] = i$ | | 3 | 7 | $c$ 是一个等差数列，即对于所有 $2 \le i \le k-1$，有 $c[i+1] - c[i] = c[i] - c[i-1]$ | | 4 | 9 | $h, w, k \le 8$ | | 5 | 31 | $h, w, k \le 3000$ | | 6 | 16 | 对于所有 $1 \le i < j \le k$，有 $c[i] \ne c[j]$ | | 7 | 27 | 无额外约束 | 翻译由 DeepSeek 完成