在 NOI 2023 之后，猴子 Pan 从兔子 Benson 手中接管了一架飞机。
在飞机上，乘客座位排列成 $h$ 行 $w$ 列。行从上到下依次编号为 $1$ 到 $h$，列从左到右依次编号为 $1$ 到 $w$。我们用 $(i, j)$ 表示位于第 $i$ 行第 $j$ 列的座位。
CEO Pan 向 $k$ 名乘客售出了机票，乘客的编号为 $1$ 到 $k$。第 $i$ 名乘客有其偏好的列 $c[i]$，但 Pan 可以为其分配任意行 $r[i]$ 供其就坐。任意两名乘客不能占用同一个座位。
为了在飞机上保持均匀的重量分布，坐在较前行（行号较小）的乘客不能坐在较后列（列号较大）中。正式地，对于任意两个已分配的座位 $(a_1, b_1)$ 和 $(a_2, b_2)$，如果 $a_1 < a_2$，则必须满足 $b_1 \le b_2$。
CEO Pan 将“总乘客满意度”（Gross Passenger Satisfaction）定义为所有已分配座位对之间的最小曼哈顿距离。一对座位 $(a_1, b_1)$ 和 $(a_2, b_2)$ 之间的曼哈顿距离为 $|a_1 - a_2| + |b_1 - b_2|$，其中 $|x|$ 表示 $x$ 的绝对值。
请帮助 Pan 确定在所有合法的行分配方案中，可能达到的最大“总乘客满意度”；或者判断是否存在合法的行分配方案。
输入格式
本题从标准输入读取数据。
第一行包含三个空格分隔的整数 $h$、$w$ 和 $k$。
第二行包含 $k$ 个空格分隔的整数 $c[1], c[2], \dots, c[k]$。
输出格式
本题输出到标准输出。
输出一个整数，表示最大的总乘客满意度。如果不存在合法的行分配方案，则输出 $-1$。
数据范围
对于所有测试数据，输入满足以下范围：
- $1 \le h, w \le 10^9$
- $2 \le k \le 200\,000$
- $1 \le c[i] \le w$ 对于所有 $1 \le i \le k$
您的程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 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] \neq c[j]$ |
| 7 | 27 | 无附加限制 |
样例
输入格式 1
5 1 6 1 1 1 1 1 1
输出格式 1
-1
说明 1
飞机有 $h = 5$ 行和 $w = 1$ 列。机舱内总共有 $5 \times 1 = 5$ 个座位。因此，Pan 不可能为 $k = 6$ 名乘客分配互不相同的座位。
输入格式 2
2 7 3 1 2 3
输出格式 2
1
输入格式 3
3 7 3 1 4 7
输出格式 3
4
输入格式 4
50 50 10 34 21 28 44 41 28 5 10 16 24
输出格式 4
9
输入格式 5
4 11 5 1 1 11 7 3
输出格式 5
2
说明 5
上图展示了其中一种使总乘客满意度最大化的合法行分配方案。每个画叉的格子表示该座位分配给了一名乘客。第一名乘客被分配到第 1 行，其余乘客被分配到第 4 行。
乘客 2（座位 $(4, 1)$）与乘客 5（座位 $(4, 3)$）之间的曼哈顿距离为 $|4-4|+|1-3| = 2$，这是所有乘客对之间的最小值。因此，该分配方案的总乘客满意度为 2。
上图展示了一个不合法行分配方案的例子。尽管该分配方案中的总乘客满意度为 3，但乘客 3（座位 $(1, 11)$）和乘客 4（座位 $(3, 7)$）会导致重量分布不均，因为乘客 3 坐在较前的行，却坐在较后的列。