The city of Jakarta has skyscrapers located on a line, conveniently numbered
through
from left to right. There are no other skyscrapers in Jakarta.
Jakarta is inhabited by mystical creatures called "doge"s. The doges are conveniently numbered
through
. Doge
initially resides in skyscraper
. Doge
has a mystical power, represented with a positive integer
. This mystical power enables doges to jump between skyscrapers. In a single jump, a doge with superpower
that is currently in skyscraper
can move to either skyscraper
(if
) or skyscraper
(if
).
Doge is the most awesome doge, and it is the leader of all the doges. It has an urgent news for doge
, and wants the news to reach doge
as quickly as possible. Any doge that has received the news can do any of the following actions:
- Make a jump to move to some other skyscraper.
- Pass the news to another doge in the same skyscraper.
Please help the doges by calculating the minimum number of total jumps required by all doges to pass the news to doge , or if it is impossible to do so.
Input Specification
The first line contains two integers and
. Each of the next
lines contains two integers
and
.
Output Specification
A single line containing the minimum number of total jumps, or -1
if it is impossible.
Sample Input
5 3
0 2
1 1
4 1
Sample Output
5
Explanation for Sample Output
Here is one of the possible scenarios to pass the news using jumps:
- Doge
jumps to skyscraper
and then to skyscraper
(
jumps).
- Doge
passes the news to doge
.
- Doge
jumps to skyscraper
, and then to skyscraper
, and then to skyscraper
(
jumps).
- Doge
passes the news to doge
.
Subtasks
For each subtask,
Comments