Սակուրակո և նրա ճանապարհորդությունը#407

Սակուրակո և նրա ճանապարհորդությունը

1 վայրկյան
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;

  • ( միավոր): առանց լրացուցիչ սահմանափակումների.