Yığım
Fiksiya sakinlərinin hər şeydən kifayət qədər var idi! Şəhər getdikcə daha da böyüyür və daha da darıxdırıcı olur. Fiksiya yalnız üfüqi və şaquli küçələrdən ibarətdir. Hər bir cüt qonşu paralel küçə arasındakı məsafə həmişə eynidir və biz bunu məsafə vahidi kimi qəbul edəcəyik. Bəlkə bəzi dəyişikliklər zərər verməz?
Daha çox dəstək cəlb etmək və onların narazılığını bələdiyyəyə bildirmək üçün bir qrup vətəndaş şəhərin kəsişməsində etiraz üçün toplaşmağa razılaşdı. Sual yaranır: hansı kəsişmə? Çünki aralarında böyük fərq yoxdur, hər kəsin keçməli olduğu ümumi məsafəni minimallaşdıran (x', y') kəsişməsini seçmək ideyası irəli sürüldü. Çünki hamı kəsişməyə yaxın yaşayır, (x, y) ünvanında yaşayan birinin keçdiyi fərdi məsafə |x - x'| + |y - y'| olacaq.
Lakin bu, uzaqda yaşayan insanlar üçün problem yarada bilər, çünki onların ora vaxtında çatması çətin ola bilər. Buna görə qərara alındı ki, kəsişmə hər kəsdən müəyyən bir d məsafəsindən çox olmamalıdır. Bu məhdudiyyəti nəzərə alaraq, hər bir sakinin keçməli olduğu ümumi məsafəni minimallaşdıran kəsişməni müəyyən etməyə kömək etməlisiniz.
Giriş məlumatları
Aşağıdakılardan ibarətdir:
bir sıra n (2 ≤ n ≤ 100000) - vətəndaşların sayı;
n sıra, hər biri iki tam ədəd x və y (0 ≤ x, y ≤
10^9) - hər bir sakinin evinin koordinatları;bir sıra tam ədəd d (0 ≤ d ≤ 2 *
10^9) - hər bir sakinin keçə biləcəyi ən böyük məsafə.
Bir neçə sakin eyni kəsişmədə yaşaya bilər.
Çıxış məlumatları
Bir tam ədəd çıxarın: bütün vətəndaşların keçməli olduğu minimal mümkün ümumi məsafə. Əgər kəsişmə mövcud deyilsə, yəni hamı d məsafəsindən çox məsafədə yaşayırsa, "impossible" çıxarın.