RightAnglelesdə Atəşfəşanlıq
Şəhər RightAngleles sonsuz kvadrat şəbəkə şəklində tikilmiş küçələrə malikdir. Bu küçələr ya bir-birinə paralel, ya da perpendikulyardır və ən yaxın paralel küçələr arasındakı məsafə eynidir (bu məsafəni bir vahid olaraq qəbul edək). Qərb-Şərq istiqamətində yerləşən küçələr üfüqi küçələr adlanır və Cənub-Şimal istiqamətində ardıcıl tam ədədlərlə nömrələnir. Cənub-Şimal istiqamətində yerləşən küçələr isə şaquli küçələr adlanır və Qərb-Şərq istiqamətində ardıcıl tam ədədlərlə nömrələnir.
Hər bir vətəndaş müəyyən bir üfüqi və şaquli küçənin kəsişməsində yerləşən bir evdə yaşayır. Eyni evdə bir neçə vətəndaş yaşaya bilər.
RightAngleles şəhərinin meri, əsas üfüqi küçənin (nömrəsi 0 olan) və müəyyən bir şaquli küçənin kəsişməsində atəşfəşanlıq təşkil edərək populyarlığını artırmaq istəyir. Atəşfəşanlığa gəlmək və zövq almaq istəyən vətəndaşların harada yaşadığı məlumdur. Atəşfəşanlıq həm kəsişmədə yerləşən küçələr boyunca görünəcək; əlavə olaraq, təhlükəsizlik səbəblərinə görə müşahidəçilər atəşfəşanlıq baş verən kəsişmədən ən azı S vahid uzaqda olmalıdırlar. Beləliklə, əgər atəşfəşanlıq şaquli küçə V ilə kəsişmədə baş verəcəksə, hər bir maraqlı vətəndaş əsas üfüqi küçədə (nömrəsi 0 olan) və ya şaquli küçə V üzərində S vahiddən daha yaxın olmayan bir kəsişməyə gəlməlidir. Məsələn, əgər S=2 olarsa, müşahidə V-1, V və V+1 küçələri ilə kəsişənlər istisna olmaqla əsas üfüqi küçənin istənilən kəsişməsindən və şaquli küçə V üzərində -1, 0 və 1 üfüqi küçələri ilə kəsişənlər istisna olmaqla bütün kəsişmələrdən edilə bilər.
Atəşfəşanlığın ümumi müsbət təsiri vətəndaşların nümayişi izləmək üçün hərəkət etməli olduqları ümumi məsafə ilə sıx bağlıdır. Buna görə də, atəşfəşanlıq üçün kəsişmə bu ümumi məsafəni minimuma endirmək üçün seçilməlidir.
Məsələn, əgər S=2 və yeddi vətəndaş varsa, onların yerləri xəritədə göstərilib (onlardan ikisi (-4;8) nöqtəsindədir), onda atəşfəşanlıq üçün ən yaxşı yer əsas küçənin 8-ci şaquli küçə ilə kəsişməsidir; bu halda vətəndaşların hərəkət etməli olduqları ümumi məsafə 9 vahiddir.
Vətəndaşların atəşfəşanlığı izləmək üçün hərəkət etməli olduqları minimum mümkün ümumi məsafəni (vahidlərdə) hesablayan bir proqram yazın.
Giriş verilənləri
Giriş məlumatları fire.in mətn faylında verilir. Birinci sətir boşluqla ayrılmış iki müsbət tam ədəd ehtiva edir: vətəndaşların sayı N (N ≤ 10^5) və təhlükəsizlik məsafəsi S (S ≤ 10^6) vahidlərdə. Növbəti N sətir vətəndaşların yerlərinin təsvirlərini ehtiva edir. Bu sətirlərin hər biri boşluqla ayrılmış iki tam ədəd H_i və V_i ehtiva edir; H_i və V_i (-10^9 ≤ H_i,V_i ≤ 10^9) i-ci vətəndaşın evinin girişi yerləşən kəsişmənin üfüqi və şaquli küçələrinin nömrələrini göstərir.
Çıxış verilənləri
fire.out mətn faylının birinci və yeganə sətri vətəndaşların atəşfəşanlığı izləmək üçün hərəkət etməli olduqları minimum ümumi məsafəni (vahidlərdə) göstərən dəqiq bir tam ədəd ehtiva etməlidir.