Sakurako və Onun Səyahəti#407

Sakurako və Onun Səyahəti

1 saniyə
256 meqabayt
Hard

Bu yay, Sakurako yeni bir ölkəyə səfər etməyə qərar verdi. Gəldikdən sonra, onun tur bələdçisi ona, pul xərcləməsinə səbəb olacaq turist tələsi haqqında xəbərdarlıq etdi. Sakurakonun olduğu şəhər n\times n kvadrat şəbəkə kimi təsvir oluna bilər.

Hazırda, o, mövqeyindədir. Onun məqsədi mövqeyində yerləşən hava limanına çatmaqdır. Səyahəti zamanı, o, bütün turist tələlərindən mümkün qədər uzaqda olmaq istəyir.

Hər turist tələsinin mövqeyi (x_i, y_i) kimi verilir. Sakurakonun hazırki mövqeyindən (x_S, y_S) -ci turist tələsinə olan məsafə D(i, x_S, y_S)=|x_i-x_S|+|y_i-y_S| kimi hesablanır.

O, şəbəkə boyunca səyahət edərkən, istənilən qonşu mövqeyə ( (x, y)\to (x+1,y); (x-1,y); (x,y-1); (x,y+1)) keçə bilər, yeni mövqeyin şəbəkədə etibarlı mövqe olması şərti ilə (1\le x_{new},y_{new}\le n).

Gəlin çoxluğu, Sakurakonun səyahəti zamanı ziyarət etdiyi bütün mövqeləri təmsil etsin.

Sizin tapşırığınız \displaystyle\min\limits_{\underset{(x,y)\in S}{i\in[1,m]}}D(i,x,y) ifadəsini maksimuma çatdırmaqdır.

Başqa sözlə, siz Sakurakonun səyahətini elə seçməlisiniz ki, səyahət zamanı bütün turist tələlərinə minimal məsafəni maksimuma çatdırasınız. Siz mümkün olan maksimum minimal məsafəni çıxışa verməlisiniz.

Input

İlk sətirdə iki tam ədəd (2\le n \le 10^9; 1\le m\le 5\,000) — şəbəkənin ölçüsü və şəhərdəki turist tələlərinin sayı verilir.

Sonrakı sətrin hər biri iki tam ədəd ehtiva edir: 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)), hansı ki, nömrəli turist tələsinin mövqeyini göstərir.

Output

Siz bir tam ədəd çıxarmalısınız — tapşırığın cavabı.

Examples

Example 1

Loading
Loading

Note

İlk nümunə üçün optimal yollardan biri.

Scoring

  1. ( bal): n,m\le 100;

  2. ( bal): n,m\le 10^3;

  3. ( bal): n \le 10^3;

  4. ( bal): ya x_1=x_2=\dots=x_m ya da y_1=y_2=\dots=y_m;

  5. ( bal): əlavə məhdudiyyətlər olmadan.