You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

六王毕，四海一；蜀山兀，阿房出。覆压三百余里，隔离天日。骊山北构而西折，直走咸阳。二川溶溶，流入宫墙。五步一楼，十步一阁；廊腰缦回，檐牙高啄；各抱地势，钩心斗角。盘盘焉，囷囷焉，蜂房水涡，矗不知其几千万落。长桥卧波，未云何龙？复道行空，不霁何虹？高低冥迷，不知西东。歌台暖响，春光融融；舞殿冷袖，风雨凄凄。一日之内，一宫之间，而气候不齐。

妃嫔媵嫱，王子皇孙，辞楼下殿，辇来于秦，朝歌夜弦，为秦宫人。明星荧荧，开妆镜也；绿云扰扰，梳晓鬟也；渭流涨腻，弃脂水也；烟斜雾横，焚椒兰也。雷霆乍惊，宫车过也；辘辘远听，杳不知其所之也。一肌一容，尽态极妍，缦立远视，而望幸焉；有不见者，三十六年。

燕、赵之收藏，韩、魏之经营，齐、楚之精英，几世几年，剽掠其人，倚叠如山；一旦不能有，输来其间。鼎铛玉石，金块珠砾，弃掷逦迤，秦人视之，亦不甚惜。

嗟乎！一人之心，千万人之心也。秦爱纷奢，人亦念其家；奈何取之尽锱铢，用之如泥沙？使负栋之柱，多于南亩之农夫；架梁之椽，多于机上之工女；钉头磷磷，多于在庾之粟粒；瓦缝参差，多于周身之帛缕；直栏横槛，多于九土之城郭；管弦呕哑，多于市人之言语。使天下之人，不敢言而敢怒；独夫之心，日益骄固。戍卒叫，函谷举；楚人一炬，可怜焦土。

呜呼！灭六国者六国也，非秦也；族秦者秦也，非天下也。嗟乎！使六国各爱其人，则足以拒秦；使秦复爱六国之人，则递三世可至万世而为君，谁得而族灭也？秦人不暇自哀，而后人哀之；后人哀之而不鉴之，亦使后人而复哀后人也。

题目描述

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

有 $M$ 只叫做 “doge” 的神秘生物在雅加达市居住，它们的编号依次是 $0$ 到 $M − 1$。编号为 $i$ 的 doge 最初居住于编号为 $B_i$ 的摩天楼。每只 doge 都有一种神秘的力量，使它们能够在摩天楼之间跳跃，编号为 $i$ 的 doge 的跳跃能力为 $P_i$ （$P_i > 0$）。

在一次跳跃中，位于摩天楼 $b$ 而跳跃能力为 $p$ 的 doge 可以跳跃到编号为 $b - p$ （如果 $0 \leq b - p < N$）或 $b + p$ （如果 $0 \leq b + p < N$）的摩天楼。

编号为 $0$ 的 doge 是所有 doge 的首领，它有一条紧急的消息要尽快传送给编号为 $1$ 的 doge。任何一个收到消息的 doge 有以下两个选择:

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

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

输入格式

输入的第一行包含两个整数 $N$ 和 $M$。

接下来 $M$ 行，每行包含两个整数 $B_i$ 和 $P_i$。

输出格式

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

5 3
0 2
1 1
4 1

5

说明/提示

【样例解释】

下面是一种步数为 $5$ 的解决方案：

$0$ 号 doge 跳跃到 $2$ 号摩天楼，再跳跃到 $4$ 号摩天楼（$2$ 步）。

$0$ 号 doge 将消息传递给 $2$ 号 doge。

$2$ 号 doge 跳跃到 $3$ 号摩天楼,接着跳跃到 $2$ 号摩天楼，再跳跃到 $1$ 号摩天楼（$3$ 步）。

$2$ 号 doge 将消息传递给 $1$ 号 doge。

【数据范围】

所有数据都保证 $0 \leq B_i < N$。

子任务 1 （10 分）$1 \leq N \leq 10$

$1 \leq P_i \leq 10$

$2 \leq M \leq 3$

子任务 2 （12 分）$1 \leq N \leq 100$

$1 \leq P_i \leq 100$

$2 \leq M \leq 2000$

子任务 3 （14 分）$1 \leq N \leq 2000$

$1 \leq P i ≤ 2000$

$2 \leq M \leq 2000$

子任务 4 （21 分）$1 \leq N \leq 2000$

$1 \leq P_i \leq 2000$

$2 \leq M \leq 30000$

子任务 5 （43 分）$1 \leq N \leq 30000$

$1 \leq P_i \leq 30000$

$2 \leq M \leq 30000$