APIO '15 P2 - Jakarta Skyscrapers - DMOJ: Modern Online Judge

APIO '15 P2 - Jakarta Skyscrapers

Points: 20 (partial)

Time limit: 0.2s

Memory limit: 256M

Problem type

The city of Jakarta has $N$ $N$ skyscrapers located on a line, conveniently numbered $0$ $0$ through $N-1$ $N - 1$ from left to right. There are no other skyscrapers in Jakarta.

Jakarta is inhabited by $M$ $M$ mystical creatures called "doge"s. The doges are conveniently numbered $0$ $0$ through $M-1$ $M - 1$ . Doge $i$ $i$ initially resides in skyscraper $B_i$ $B_{i}$ . Doge $i$ $i$ has a mystical power, represented with a positive integer $P_i$ $P_{i}$ . This mystical power enables doges to jump between skyscrapers. In a single jump, a doge with superpower $p$ $p$ that is currently in skyscraper $b$ $b$ can move to either skyscraper $b+p$ $b + p$ (if $0 \le b+p < N$ $0 \leq b + p < N$ ) or skyscraper $b-p$ $b - p$ (if $0 \le b-p < N$ $0 \leq b - p < N$ ).

Doge $0$ $0$ is the most awesome doge, and it is the leader of all the doges. It has an urgent news for doge $1$ $1$ , and wants the news to reach doge $1$ $1$ 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 $1$ $1$ , or if it is impossible to do so.

Input Specification

The first line contains two integers $N$ $N$ and $M$ $M$ . Each of the next $M$ $M$ lines contains two integers $B_i$ $B_{i}$ and $P_i$ $P_{i}$ .

Output Specification

A single line containing the minimum number of total jumps, or -1 if it is impossible.

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

Here is one of the possible scenarios to pass the news using $5$ $5$ jumps:

Doge $0$ $0$ jumps to skyscraper $2$ $2$ and then to skyscraper $4$ $4$ ( $2$ $2$ jumps).
Doge $0$ $0$ passes the news to doge $2$ $2$ .
Doge $2$ $2$ jumps to skyscraper $3$ $3$ , and then to skyscraper $2$ $2$ , and then to skyscraper $1$ $1$ ( $3$ $3$ jumps).
Doge $2$ $2$ passes the news to doge $1$ $1$ .

Subtasks

For each subtask,

$0 \le B_i < N$ $0 \leq B_{i} < N$

Subtask 1 (10 points)

$1 \le N \le 10$ $1 \leq N \leq 10$
$1 \le P_i \le 10$ $1 \leq P_{i} \leq 10$
$2 \le M \le 3$ $2 \leq M \leq 3$

Subtask 2 (12 points)

$1 \le N \le 100$ $1 \leq N \leq 100$
$1 \le P_i \le 100$ $1 \leq P_{i} \leq 100$
$2 \le M \le 2\,000$ $2 \leq M \leq 2 000$

Subtask 3 (14 points)

$1 \le N \le 2\,000$ $1 \leq N \leq 2 000$
$1 \le P_i \le 2\,000$ $1 \leq P_{i} \leq 2 000$
$2 \le M \le 2\,000$ $2 \leq M \leq 2 000$

Subtask 4 (21 points)

$1 \le N \le 2\,000$ $1 \leq N \leq 2 000$
$1 \le P_i \le 2\,000$ $1 \leq P_{i} \leq 2 000$
$2 \le M \le 30\,000$ $2 \leq M \leq 30 000$

Subtask 5 (43 points)

$1 \le N \le 30\,000$ $1 \leq N \leq 30 000$
$1 \le P_i \le 30\,000$ $1 \leq P_{i} \leq 30 000$
$2 \le M \le 30\,000$ $2 \leq M \leq 30 000$

Comments

There are no comments at the moment.