Jakarta có \(N\) tòa nhà chọc trời nằm trên một đường thẳng, đánh số từ \(0\) đến \(N-1\) từ trái sang phải.

Có \(M\) sinh vật gọi là doge, đánh số từ \(0\) đến \(M-1\). Ban đầu doge \(i\) ở tòa nhà \(B_i\) và có năng lượng \(P_i\). Trong một bước nhảy, doge có năng lượng \(p\) đang ở tòa nhà \(b\) có thể nhảy đến \(b+p\) hoặc \(b-p\), miễn là tòa nhà đích có số hiệu trong \([0,N-1]\).

Doge \(0\) cần truyền một tin khẩn cấp tới doge \(1\). Sau khi nhận tin, một doge có thể:

• thực hiện một bước nhảy; hoặc
• truyền tin cho một doge khác đang ở cùng tòa nhà.

Hãy tìm tổng số bước nhảy ít nhất mà tất cả doge phải thực hiện để tin đến được doge \(1\), hoặc cho biết việc đó không thể thực hiện.

Dữ liệu vào

• Dòng đầu chứa \(N,M\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(B_i,P_i\).

Dữ liệu ra

In tổng số bước nhảy nhỏ nhất, hoặc -1 nếu không thể truyền tin.

Ràng buộc chung

• \(0\le B_i<N\).
• \(M\ge2\).

Ví dụ

5 3
0 2
1 1
4 1

5

Giải thích

Doge \(0\) nhảy từ tòa nhà \(0\) đến \(2\), rồi đến \(4\) trong hai bước và truyền tin cho doge \(2\). Doge \(2\) nhảy từ \(4\) đến \(3\), \(2\), rồi \(1\) trong ba bước và truyền tin cho doge \(1\). Tổng cộng có năm bước nhảy.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2015, bài Jakarta Skyscrapers.