← 返回题目列表

AtCoder · abc379_c

F. 播种石头

中文机器翻译题面 查看原题

分数: 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.