[APIO2015-B]雅加达的摩天楼

内存限制：256 MB 时间限制：1000 ms

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

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

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

跳跃到其他摩天楼上；
将消息传递给它当前所在的摩天楼上的其他 doge。

请帮助 doge 们计算将消息从 $0$ 号 doge 传递到 $1$ 号 doge 所需要的最少总跳跃步数，或者告诉它们消息永远不可能传递到 $1$ 号 doge。

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

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

样例输入 1

样例输出 1

【样例解释】

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

0 号 doge 跳跃到 2 号摩天楼，再跳跃到 4 号摩天楼（2 步）。

0 号 doge 将消息传递给 2 号 doge。

2 号 doge 跳跃到 3 号摩天楼，接着跳跃到 2 号摩天楼，再跳跃到 1 号摩天楼（3 步）。

2 号 doge 将消息传递给 1 号 doge。

【数据规模和约定】（comet 不支持APIO评分方式）

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

第1部分数据（测试点 1-6）占10分，数据范围满足：$1 \le N \le 10，1 \le P_i \le 10，2 \le M \le 3$

第2部分数据（测试点 7-14）占12分，数据范围满足：$1 \le N \le 100，1 \le P_i \le 100，2 \le M \le 2000$

第3部分数据（测试点 15-33）占14分，数据范围满足：$1 \le N \le 2000，1 \le P_i \le 2000，2 \le M \le 2000$

第4部分数据（测试点 34-45）占21分，数据范围满足：$1 \le N \le 2000，1 \le P_i \le 2000，2 \le M \le 30000$

第5部分数据（测试点 46-66）占43分，数据范围满足：$1 \le N \le 30000，1 \le P_i \le30000，2 \le M \le 30000$