题目描述

$Bob$ 最近对 “移动石子” 游戏特别感兴趣，游戏规则如下：

有 $n$ 个格子排成一列，$m$ 个格子上有石子，第 $X_i$ 个格子上有 $A_i$ 个石子。

$Bob$ 一次操作如下定义：

• 对于第 $i$ 个格子，如果这个格子上有石子 ，可以将这个格子的一个石子移动到第 $i+1$ 个格子上。

求使得每个格子上恰有一个石子的最少移动次数（可以不移动，那么移动次数就是 $0$ ），如果无法满足完成目标输出 $-1$。

输入格式

输入参数与题目描述含义相同。

• 第一行：$N$ $M$

• 第二行：$X_1$ $X_2$ $\dots$ $X_M$

• 第三行：$A_1$ $A_2$ $\dots$ $A_M$

输出格式

第一行一个数，表示移动的最少次数，如果无法达到目的输出 $-1$。

5 2
1 4
3 2

4

样例 1 解释

可以通过如下 $4$ 次操作使条件满足，且没有比 $4$ 次更小的次数。

初始条件：第一个格子上有 $3$ 个石子，第四个格子上有 $2$ 个石子。

• 移动一个石子从格子 $1$ 到格子 $2$。

• 再移动一个石子从格子 $1$ 到格子 $2$。

• 移动一个石子从格子 $2$ 到格子 $3$。

• 移动一个石子从格子 $4$ 到格子 $5$。

操作完成后每个格子上都有一个石子。

10 3
1 4 8
4 2 4

-1

样例 2 解释

这个数据中无论如何移动一定无法使每个格子上有一个石子。

10 3
1 4 8
4 4 3

-1

样例3解释

$10$ 个位置， $11$ 个石子，有一个位置会超过一个 $1$ 个石子，输出 $-1$

数据规模与约定

所有数据满足：

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^{9}$
• $1\ \leq\ M\ \leq\ 2\ \times\ 10^{5}$
• $M\ \leq\ N$
• $1\ \leq\ X_1 < X_2 < \dots X_n \leq\ N$ $(1\ \leq\ i\ \leq\ M)$
• $1 \leq A_i \leq\ 2 \times 10^{9}$ $(1 \leq i \leq M)$
• 输入为整数

其中：

$subtask1$: $2 \leq M\leq N \leq 10^3$ , $1\leq A_i \leq 10^3$ , $30$ 分

$subtask2$: 无其他限制，$70$ 分