题目描述

雅加达（印尼首都）有 $N$ 座摩天楼排成一列，依次编号为 $0$ 到 $N−1$。
有 $M$ 只神秘生物 doge 住在雅加达，分别编号为 $0$ 到 $M−1$。$i$ 号 doge 最初居住于 $Bi$ 号摩天楼。
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$ 行，每行包含两个整数 $Bi$ 和 $P{\,i}$。

输出格式

输出一个整数，表示所需要的最少步数。如果消息永远无法传递到 doge $1$，输出 $\texttt{−1}$。

样例

input

5 3
0 2
1 1
4 1

output

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$