播撒石子

题目描述

有 $N$ 个单元格排成一行，编号为 $1$ 到 $N$。初始时，有 $M$ 个单元格包含石子，其中单元格 $X_i$ 包含 $A_i$ 个石子（$1 \leq i \leq M$）。

你可以执行任意次数（包括 0 次）以下操作：

• 如果单元格 $i$（$1 \leq i \leq N-1$）包含石子，将一个石子从单元格 $i$ 移动到单元格 $i+1$。

请找出将所有 $N$ 个单元格都恰好包含一个石子所需的最小操作次数。如果不可能，输出 $-1$。

输入格式

第一行输入两个整数 $N$ 和 $M$； 第二行输入 $M$ 个整数 $X_1\ X_2\ \dots\ X_M$； 第三行输入 $M$ 个整数 $A_1\ A_2\ \dots\ A_M$。

输出格式

输出一个整数，表示所需的最小操作次数；若不可能，输出 $-1$。

样例

样例输入 1

5 2
1 4
3 2

样例输出 1

4

样例解释 1

可通过以下 4 次操作使所有 5 个单元格都恰好包含一个石子：

• 将一个石子从单元格 1 移动到单元格 2。
• 将一个石子从单元格 1 移动到单元格 2；
• 将一个石子从单元格 2 移动到单元格 3；
• 将一个石子从单元格 4 移动到单元格 5；

无法在 3 次或更少操作内达成目标，因此输出 4。

样例输入 2

10 3
1 4 8
4 2 4

样例输出 2

-1

样例解释 2

无论如何操作，都无法使所有 10 个单元格都恰好包含一个石子，因此输出 $-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) $
• 所有输入值均为整数。

子任务