#4070. [Apio2015] 雅加达的摩天楼

[Apio2015] 雅加达的摩天楼

题目描述

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

MM 只叫做 “doge” 的神秘生物在雅加达市居住,它们的编号依次是 00M1M − 1。编号为 ii 的 doge 最初居住于编号为 BiB_i 的摩天楼。每只 doge 都有一种神秘的力量,使它们能够在摩天楼之间跳跃,编号为 ii 的 doge 的跳跃能力为 PiP_iPi>0P_i > 0)。

在一次跳跃中,位于摩天楼 bb 而跳跃能力为 pp 的 doge 可以跳跃到编号为 bpb − p (如果 0bp<N0 \leq b − p < N)或 b+pb + p (如果 0b+p<N0 \leq b + p < N)的摩天楼。

编号为 00 的 doge 是所有 doge 的首领,它有一条紧急的消息要尽快传送给编

号为 11 的 doge。任何一个收到消息的 doge 有以下两个选择:

跳跃到其他摩天楼上;

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

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

输入格式

输入的第一行包含两个整数 NNMM

接下来 MM 行,每行包含两个整数 BiB_iPiP_i

输出格式

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

5 3
0 2
1 1
4 1
5

样例解释

下面是一种步数为 55 的解决方案:

00 号 doge 跳跃到 22 号摩天楼,再跳跃到 44 号摩天楼(22 步)。

00 号 doge 将消息传递给 22 号 doge。

22 号 doge 跳跃到 33 号摩天楼,接着跳跃到 22 号摩天楼,再跳跃到 11 号摩天楼(33 步)。

22 号 doge 将消息传递给 11 号 doge。

数据规模与约定

所有数据都保证 0Bi<N0 \leq B_i < N

子任务 1 (10 分)1N101 \leq N \leq 10

1Pi101 \leq P_i \leq 10

2M32 \leq M \leq 3

子任务 2 (12 分)1N1001 \leq N \leq 100

1Pi1001 \leq P_i \leq 100

2M20002 \leq M \leq 2000

子任务 3 (14 分)1N20001 \leq N \leq 2000

1Pi20001 \leq P i ≤ 2000

2M20002 \leq M \leq 2000

子任务 4 (21 分)1N20001 \leq N \leq 2000

1Pi20001 \leq P_i \leq 2000

2M300002 \leq M \leq 30000

子任务 5 (43 分)1N300001 \leq N \leq 30000

1Pi300001 \leq P_i \leq 30000

2M300002 \leq M \leq 30000