分数: 300 点
问题陈述
有 N 单元格编号为 1 to N 连续。最初, M 细胞含有结石,并且细胞 X_i 包含 A_i 石头 (1 \leq i \leq M).
您可以执行以下操作任意次数(可能为零):
- 如果单元格 i (1 \leq i \leq N-1) 包含一颗石头,从单元格中移动一颗石头 i 到单元格 i+1.
找出达到每个状态所需的最少操作数 N 细胞恰好包含一颗石头。如果不可能,则打印 -1.
约束
- 2 \leq N \leq 2 \times 10^{9}
- 1 \leq M \leq 2 \times 10^{5}
- M \leq N
- 1 \leq X_i \leq N (1 \leq i \leq M)
- X_i \neq X_j (1 \leq i < j \leq M)
- 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M X_1 X_2 \ldots X_M A_1 A_2 \ldots A_M
输出
打印答案。
示例输入 1
5 2 1 4 3 2
示例输出 1
4
通过如下四次操作,您可以达到五个单元格中的每一个都恰好包含一颗石头的状态:
- 从牢房中移出一颗石头 1 到单元格 2.
- 从牢房中移出一颗石头 2 到单元格 3.
- 从牢房中移出一颗石头 4 到单元格 5.
- 从牢房中移出一颗石头 1 到单元格 2.
不可能通过三个或更少的操作来实现目标。因此,打印 4.
示例输入 2
10 3 1 4 8 4 2 4
示例输出 2
-1
无论你如何执行操作,你都无法达到所有十个单元格都恰好包含一颗石头的状态。因此,打印 -1.