ساكوركو ورحلتها#407

ساكوركو ورحلتها

ثانية
256 ميغابايت
Hard

هذا الصيف، قررت ساكوركو زيارة بلد جديد. بعد وصولها، حذرها مرشدها السياحي من فخاخ سياحية ستجعلها تنفق بعض المال. يمكن تمثيل المدينة التي تتواجد فيها ساكوركو على أنها شبكة مربعة أبعادها 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).

بعبارة أخرى، يجب أن تختار مسار رحلة ساكوركو بحيث تكون المسافة الدنيا إلى أي فخ سياحي أثناء الرحلة أكبر ما يمكن. يجب عليك إخراج أكبر قيمة ممكنة لتلك المسافة الدنيا.

Input

السطر الأول يحتوي على عددين صحيحين (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))،والتي تشير إلى موقع الفخ السياحي رقم .

Output

يجب عليك إخراج عدد صحيح واحد — الإجابة على المهمة.

Examples

Example 1

Loading
Loading

Note

أحد المسارات المثلى للمثال الأول.

Scoring

  • ( نقاط): 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;

  • ( نقاط): بدون قيود إضافية.