logo AlgoBeat OnlineJudge
登录 注册

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

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

题目描述

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

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

在一次跳跃中,位于摩天楼 而跳跃能力为 的 doge 可以跳跃到编号为 (如果 )或 (如果 )的摩天楼。

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

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

跳跃到其他摩天楼上;

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

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

输入格式

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

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

输出格式

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

样例

样例输入 #1

5 3
0 2
1 1
4 1

样例输出 #1

5

样例解释

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

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

号 doge 将消息传递给 号 doge。

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

号 doge 将消息传递给 号 doge。

数据范围与提示

所有数据都保证

子任务 1 (10 分)

子任务 2 (12 分)

子任务 3 (14 分)

子任务 4 (21 分)

子任务 5 (43 分)