Nông dân John lo lắng về sức khỏe những chú bò của anh ấy sau đợt bùng phát lây lan dịch bệnh COVID-19 ở bò.

Để hạn chế sự lây nhiễm, John quyết định "giãn cách xã hội" \(N\ (2\leq N\leq10^5)\) chú bò của mình trên nông trại. Nông trại của John có hình dạng như một đường thẳng, với \(M\ (1\leq M\leq10^5)\) đoạn đường có cỏ để chăn thả. Các con bò phải được đặt ở những điểm có tọa độ nguyên phân biệt, và các điểm đó đều phải nằm trong các bãi cỏ. Xét \(D\) là khoảng cách giữa hai chú bò gần nhau nhất. Để phòng chống lây lan dịch bệnh hiệu quả, John muốn giá trị \(D\) phải lớn nhất có thể. Nhiệm vụ của bạn là xác địch giá trị lớn nhất có thể của \(D\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N,\ M\);
• \(M\) dòng tiếp theo, mỗi dòng mô tả một đoạn bãi cỏ gồm hai số tự nhiên \(a,\ b\), với \(0\leq a\leq b\leq10^{18}\). Không có hai đoạn nào đè lên nhau hoặc tiếp xúc nhau ở các điểm đầu mút. Những con bò đứng trên các đầu mút của các đoạn vẫn được tính là đứng trên bãi cỏ.

Output

• In ra giá trị lớn nhất có thể của \(D\). Dữ liệu đảm bảo tồn tại kết quả \(D>0\).

Ví dụ

Sample input

5 3
0 2
4 7
9 9

Sample output

2