هذا الصيف، قررت ساكوركو زيارة بلد جديد. بعد وصولها، حذرها مرشدها السياحي من فخاخ سياحية ستجعلها تنفق بعض المال. يمكن تمثيل المدينة التي تتواجد فيها ساكوركو على أنها شبكة مربعة أبعادها n\times n.
حالياً، هي في الموقع . مهمتها هي الوصول إلى المطار الذي يقع في الخلية . أثناء سفرها، ترغب في أن تكون بعيدة قدر الإمكان عن جميع الفخاخ السياحية.
كل فخ سياحي له موقعه (x_i, y_i). يتم حساب المسافة من موقع ساكوركو الحالي (x_S, y_S) إلى الفخ السياحي كالتالي: D(i, x_S, y_S)=|x_i-x_S|+|y_i-y_S|.
أثناء رحلتها عبر الشبكة، يمكنها الانتقال إلى أي خلية مجاورة ((x, y)\to (x+1,y);(x-1,y);(x,y-1);(x,y+1) مع الشرط أن يكون الموقع الجديد خلية صالحة في الشبكة (1\le x_{new},y_{new}\le n)).
لتكن مجموعة كل الخلايا في الشبكة التي تزورها ساكوركو خلال رحلتها.
مهمتك هي أيجاد القيمة العظمى لـ \displaystyle\min\limits_{\underset{(x,y)\in S}{i\in[1,m]}}D(i,x,y).
بعبارة أخرى، يجب أن تختار مسار رحلة ساكوركو بحيث تكون المسافة الدنيا إلى أي فخ سياحي أثناء الرحلة أكبر ما يمكن. يجب عليك إخراج أكبر قيمة ممكنة لتلك المسافة الدنيا.
السطر الأول يحتوي على عددين صحيحين (2\le n \le 10^9; 1\le m\le 5\,000) — بعد الشبكة وعدد الفخاخ السياحية في المدينة.
كل من الأسطر التالية تحتوي على عددين صحيحين: x_i,y_i (1\le x_i, y_i\le n; (x_i,y_i)\neq(1,1); (x_i,y_i)\neq(n,n))،والتي تشير إلى موقع الفخ السياحي رقم .
يجب عليك إخراج عدد صحيح واحد — الإجابة على المهمة.
Example 1
أحد المسارات المثلى للمثال الأول.
( نقاط): n,m\le 100;
( نقاط): n,m\le 10^3;
( نقاط): n \le 10^3;
( نقاط): إما x_1=x_2=\dots=x_m أو y_1=y_2=\dots=y_m;
( نقاط): بدون قيود إضافية.