Thành phố Jakarta có $N$ toà nhà chọc trời xây dựng dọc theo đường thẳng, được đánh số từ $0$ đến $N-1$ từ trái qua phải. Ngoài ra không còn toà nhà chọc trời nào khác ở Jakarta.

Jakarta là nơi cư trú của $M$ sinh vật huyền bí được gọi là "doge". Các doge được đánh số từ $0$ đến $M-1$. Doge $i$ đầu tiên cư trú tại toà nhà chọc trời ~B_i~. Doge $i$ có năng lượng huyền bí được biểu diễn bởi số nguyên dương ~P_i~. Năng lượng huyền bí này giúp các doge có thể nhảy giữa các toà nhà chọc trời. Mỗi bước nhảy, doge với năng lượng $p$ hiện đang ở toà nhà chọc trời $b$ có thể nhảy đến toà nhà chọc trời $b+p$ (nếu ~0 \le b+p < N~) hoặc toà nhà chọc trời $b-p$ (nếu ~0 \le bp < N~).

Doge $0$ là doge đáng sợ nhất, và nó là thủ lĩnh của tất cả các doge. Nó có một tin khẩn cấp cho doge $1$, và muốn truyền tin này đến được doge $1$ sớm nhất có thể được. Mỗi doge khi nhận được tin có thể thực hiện bất cứ hành động nào trong các hành động sau đây:

• Thực hiện một bước nhảy để di chuyển đến một toà nhà chọc trời khác.
• Truyền thông tin cho doge khác ở cùng toà nhà chọc trời.

Hãy giúp các doge tính giá trị nhỏ nhất của tổng số các bước nhảy mà tất cả các doge cần thực hiện để truyền thông tin đến doge $1$, hoặc chỉ ra rằng không có cách thực hiện điều đó.

Dữ liệu

Vào từ file sky.inp. Dòng đầu tiên chứa hai số nguyên $N$ và $M$. Mỗi dòng trong số M dòng tiếp theo chứa hai số nguyên ~B_i~ và ~P_i~ ~(0 \le B_i < N)~

Kết quả

In ra file sky.out. Một dòng duy nhất chứa giá trị nhỏ nhất của tổng số các bước nhảy, hoặc $-1$ nếu không có cách truyền tin.

Ràng buộc

• Subtask $1$: ~1 ≤ N ≤ 100; 1 ≤ P_i ≤ 100; 2 ≤ M ≤ 2000~
• Subtask $2$: ~1 ≤ N ≤ 2000; 1 ≤ P_i ≤ 2000; 2 ≤ M ≤ 30000~
• Subtask $3$: ~1 ≤ N ≤ 30000; 1 ≤ P_i ≤ 30000; 2 ≤ M ≤ 30000~

Ví dụ

Dữ liệu

5 3
0 2
1 1
4 1

Kết quả

5

Giải thích

Dưới đây là một trong số các kịch bản có thể để truyền tin sử dụng $5$ bước nhảy:

• Doge $0$ nhảy tới toà nhà chọc trời $2$ và sau đó đến toà nhà chọc trời $4$ ($2$ bước nhảy).
• Doge $0$ truyền thông tin cho doge $2$.
• Doge $2$ nhảy đến toà nhà chọc trời $3$, và sau đó nhảy đến toà nhà chọc trời $2$, và tiếp đến nhảy đến toà nhà chọc trời $1$ ($3$ bước nhảy).
• Doge $2$ truyền thông tin cho doge $1$.