Qurbağa keçidi

Fiona yeni bir kompüter oyunu olan "Qurbağa Keçidi" üzərində işləyir. Bu oyunda oyunçunun vəzifəsi, qurbağanın çaydan keçməsinə kömək etməkdir. Qurbağa, çayın üzərindəki daşlardan istifadə edərək bir sahildən digərinə tullanmalıdır. Lakin, qurbağanın tullanma qabiliyyəti məhduddur, buna görə oyunçu ən uzun tullanmanı minimuma endirən optimal yolu tapmalıdır.

Fiona oyunun daha maraqlı olması üçün çaya yeni bir daş əlavə etmək imkanı yaratmaq istəyir. O, sizdən elə bir proqram yazmağı xahiş edir ki, bu proqram yeni daşı elə yerləşdirsin ki, optimal marşrut üçün lazım olan ən uzun tullanma minimuma ensin.

Giriş verilənləri

Birinci sətir iki tam ədəd ehtiva edir: $w(1\le w\le 10^9)$ — çayın eni və $n(0\le n\le 1000)$ — daşların sayı.

Sonrakı $n$ sətirin hər biri iki tam ədəd $x_i,y_i(0<x_i<w,-10^9\le y_i\le 10^9)$ — daşların koordinatlarını ehtiva edir. Bütün daşların koordinatları fərqlidir.

Çayın sahillərinin koordinatları $x=0$ və $x=w$-dir.

Çıxış verilənləri

İki həqiqi ədəd $x_{+}$ və $y_{+}(0<x_{+}<w,-10^9\le y_{+}\le 10^9)$ — əlavə edilən daşın koordinatlarını çıxarın. Bu daş optimal marşrutda lazım olan ən uzun tullanmanı minimuma endirməlidir. Əgər yeni daş optimal yolu yaxşılaşdıra bilmirsə, onda verilən məhdudiyyətlərə uyğun istənilən $x_{+}$ və $y_{+}$ cütlüyünü çıxarın, hətta mövcud daşlardan biri ilə üst-üstə düşə bilər.

Cavab üç ondalık dəqiqliklə çıxarılmalıdır.

Nümunələr