题目描述

雅加达市有 \(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 \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 的解决方案：
\(0\) 号 doge 跳跃到 \(2\) 号摩天楼，再跳跃到 \(4\) 号摩天楼（2 步）。
\(0\) 号 doge 将消息传递给 \(2\) 号 doge。
\(2\) 号 doge 跳跃到 \(3\) 号摩天楼，接着跳跃到 \(2\) 号摩天楼，再跳跃到 \(1\) 号摩天
楼（3 步）。
\(2\) 号 doge 将消息传递给 \(1\) 号 doge。

数据范围限制

共有五部分数据。所有数据都保证 \(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\)。

限制

每个测试点时限：2秒
内存限制：512MB

来源

APIO2015