#2887. 「APIO2015」雅加达的摩天楼 Jakarta Skyscrapers

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

雅加达(印尼首都)有 N 座摩天楼排成一列,依次编号为 0 N−1
M 只神秘生物 doge 住在雅加达,分别编号为 0 M−1 i 号 doge 最初居住于 B_i 号摩天楼。
doge 能够在摩天楼间跳跃, i 号 doge 的弹跳力为 P_{\,i} (P_{\,i}>0) 。每次跳跃,位于 b 号摩天楼、弹跳力为 p 的 doge 只能跳跃到 b-p 号(若 0\le b-p\le N )或 b+p 号(若 0\le b+p\le N )摩天楼。
0 号 doge 有一条紧急的消息要尽快传送给 1 号 doge。任何一个收到消息的 doge 可以跳跃到其他摩天楼上,也可以将消息传递给它当前所在的摩天楼上的其他 doge。
请帮助 doge 们计算:将消息从 0 号 doge 传递到 1 号 doge 的最少跳跃步数,或者告诉它们消息永远不可能传递到 1 号 doge 。

输入格式

第一行有两个整数 N M
接下来 M 行,每行包含两个整数 B_i P_{\,i}

输出格式

输出一个整数,表示所需要的最少步数。如果消息永远无法传递到 doge 1 ,输出 \texttt{−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

数据范围与提示

所有数据都保证 0≤B_i<N

子任务 1 (10 分)

  • 1≤N≤10
  • 1≤P_i≤10
  • 2≤M≤3

子任务 2 (12 分)

  • 1≤N≤100
  • 1≤P_i≤100
  • 2≤M≤2000

子任务 3 (14 分)

  • 1≤N≤2000
  • 1≤P_i≤2000
  • 2≤M≤2000

子任务 4 (21 分)

  • 1≤N≤2000
  • 1≤P_i≤2000
  • 2≤M≤30000

子任务 5 (43 分)

  • 1≤N≤30000
  • 1≤P_i≤30000
  • 2≤M≤30000