题目描述

在 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$。

5 1 6
1 1 1 1 1 1

-1

2 7 3
1 2 3

1

3 7 3
1 4 7

4

50 50 10
34 21 28 44 41 28 5 10 16 24

9

4 11 5
1 1 11 7 3

2

提示

样例测试用例 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$

你的程序将在满足以下限制的输入实例上进行测试：

翻译由 DeepSeek 完成