题目描述

印尼首都雅加达市有 $N$ 座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为 $0$ 到 $N-1$ 。除了这 $N$ 座摩天楼外，雅加达市没有其他摩天楼。

有 $M$ 只叫做 “doge” 的神秘生物在雅加达市居住，它们的编号依次是 $0$ 到 $M-1$ 。编号为 $i$ 的 doge 最初居住于编号为 $B_i$ 的摩天楼。每只 doge 都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为 $i$ 的 doge 的跳跃能力为 $P_i$ $\left(P_i>0\right)$ 。在一次跳跃中，位于摩天楼 $b$ 而跳跃能力为 $p$ 的 doge 可以跳跃到编号为 $b-$ $p$（如果 $0 \leq b-p<N$ ）或 $b+p$（如果 $0 \leq b+p<N$ ）的摩天楼。

编号为 $0$ 的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编号为 $1$ 的 doge。任何一个收到消息的 doge 有以下两个选择：

1. 跳跃到其他摩天楼上；
2. 将消息传递给它当前所在的摩天楼上的其他 doge。 请帮助 doge 们计算将消息从 $0$ 号 doge 传递到 $1$ 号 doge 所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到 $1$ 号 doge。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$。接下来 $M$ 行，每行包含两个整数 $B_i$ 和 $P_i$。

输出格式

输出一行，表示所需要的最少步数。如果消息永远无法传递到 $1$ 号 doge，输出 $-1$。

5 3
0 2
1 1
4 1

5

下面是一种步数为 $5$ 的解决方案：

doge $0$ 跳跃到 $2$ 号摩天楼，再跳跃到 $4$ 号摩天楼（$2$ 步）。
doge $0$ 将消息传递给 doge $2$ 。
doge $2$ 跳跃到 $3$ 号摩天楼，接着跳跃到 $2$ 号摩天楼，再跳跃到 $1$ 号摩天楼（$3$ 步）。
doge $2$ 将消息传递给 doge $1$ 。

数据规模和约定

共有五部分数据（或称 5 个子任务）。所有数据都保证 $0 \leq B_i<N$。

第1 部分数据占 10 分，数据范围满足： $1 \leq N \leq 10,1 \leq P_i \leq 10,2 \leq M \leq 3$；
第 2 部分数据占 12 分，数据范围满足： $1 \leq N \leq 100,1 \leq P_i \leq 100,2 \leq M \leq 2000$；
第 3 部分数据占 14 分，数据范围满足： $1 \leq N \leq 2000,1 \leq P_i \leq 2000,2 \leq M \leq 2000$；
第 4 部分数据占 21 分，数据范围满足： $1 \leq N \leq 2000,1 \leq P_i \leq 2000,2 \leq M \leq 30000$；
第 5 部分数据占 43 分，数据范围满足： $1 \leq N \leq 30000,1 \leq P_i \leq 30000, 2 \leq M \leq 30000$。