103792: [Atcoder]ABC379 C - Sowing Stones

Problem Statement

There are $N$ cells numbered from $1$ to $N$ in a row. Initially, $M$ cells contain stones, and cell $X_i$ contains $A_i$ stones $(1 \leq i \leq M)$.

You can perform the following operation any number of times (possibly zero):

• If cell $i$ ($1 \leq i \leq N-1$) contains a stone, move one stone from cell $i$ to cell $i+1$.

Find the minimum number of operations required to reach a state where each of the $N$ cells contains exactly one stone. If it is impossible, print $-1$.

Constraints

• $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)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$X_1$ $X_2$ $\ldots$ $X_M$
$A_1$ $A_2$ $\ldots$ $A_M$

Output

Print the answer.

Sample Input 1

5 2
1 4
3 2

Sample Output 1

4

You can reach a state where each of the five cells contains exactly one stone with four operations as follows:

• Move one stone from cell $1$ to cell $2$.
• Move one stone from cell $2$ to cell $3$.
• Move one stone from cell $4$ to cell $5$.
• Move one stone from cell $1$ to cell $2$.

It is impossible to achieve the goal in three or fewer operations. Therefore, print $4$.

Sample Input 2

10 3
1 4 8
4 2 4

Sample Output 2

-1

No matter how you perform the operations, you cannot reach a state where all ten cells contain exactly one stone. Therefore, print $-1$.

问题陈述

有一排编号从1到N的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$。