[Apio2015]雅加达的摩天楼

时间限制:10s      空间限制:256MB

题目描述

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

有 M 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 0 到 M−1。编号为 i 的 doge 最初居住于编号为 Bi 的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为 i 的 doge 的跳跃能力为 Pi (Pi>0)。
在一次跳跃中,位于摩天楼 b 而跳跃能力为 p 的 doge 可以跳跃到编号为 b−p (如果 0≤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 行,每行包含两个整数 Bi 和 Pi。


输出格式

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


样例输入

5 3
0 2
1 1
4 1

样例输出

5
explanation
下面是一种步数为 5 的解决方案:
0 号 doge 跳跃到 2 号摩天楼,再跳跃到 4 号摩天楼(2 步)。
0 号 doge 将消息传递给 2 号 doge。
2 号 doge 跳跃到 3 号摩天楼,接着跳跃到 2 号摩天楼,再跳跃到 1 号摩天楼(3 步)。
2 号 doge 将消息传递给 1 号 doge。

提示

 子任务

所有数据都保证 0≤Bi<N。
子任务 1 (10 分)
1≤N≤10
1≤Pi≤10
2≤M≤3
子任务 2 (12 分)
1≤N≤100
1≤Pi≤100
2≤M≤2000
子任务 3 (14 分)
1≤N≤2000
1≤Pi≤2000
2≤M≤2000
子任务 4 (21 分)
1≤N≤2000
1≤Pi≤2000
2≤M≤30000
子任务 5 (43 分)
1≤N≤30000
1≤Pi≤30000
2≤M≤30000


题目来源

没有写明来源