Hədiyyə#5278
14 avqustda dünyada iki gözəl bayram qeyd olunur: A, A', və B paralelləri arasında Beynəlxalq Komanda Proqramlaşdırma Olimpiadası və LKS-də Qızlar Günü. Bu gün münasibətilə yuxarı paralellərin şagirdləri sevimli düşərgə yoldaşlarını limitsiz Wi-Fi ilə sevindirmək qərarına gəldilər. LKS-dəki evlər tərəfləri koordinat oxlarına paralel olan düzbucaqlılardır, heç biri oxunu (yəni y = 0 düz xəttini) kəsmir.
Yerli provayderlə uğurlu danışıqlardan sonra şagirdlər bir neçə router və qəbuledici əldə etdilər. Provayder isə bütün routerlərin ən yaxın yolun yaxınlığında (yəni y = 0 xətti) yerləşdirilməsini tələb etdi. Routerlər bir-birləri ilə düz xətt boyunca kabel vasitəsilə birləşdirilməlidir və müdaxilənin qarşısını almaq üçün bütün kabellərin uzunluğu -dan artıq olmamalıdır.
Bir router provayderdən interneti qəbul edir və onu digər routerlərə kabel vasitəsilə ötürür. Hər router radiusunda simsiz internet yayır. Evdə internet olması üçün evin daxilində qəbuledicinin elə nöqtədə yerləşdirilməsi lazımdır ki, bu nöqtə ən azı bir routerin yayım radiusunda olsun. Bir router istənilən sayda qəbulediciyə xidmət göstərə bilər.
Demək olar ki, bütün pullar kola və peçenyelərə xərcləndiyindən, şagirdlər icarəyə götürüləcək routerlərin sayını minimuma endirmək istəyirlər (qəbuledicilər pulsuz verilir). Onlara lazım olan minimum router sayını müəyyənləşdirməyə kömək edin.
Birinci sətrdə üç tam ədəd var: 1 \leq N \leq 100\,000 — evlərin sayı və 1 \leq dv, dh \leq 100\,000 — routerin yayım radiusu və maksimal kabel uzunluğu. Sonrakı sətrin hər birində dörd tam ədəd x_1, y_1, x_2, y_2 verilir (x_1 < x_2, y_1 < y_2), bu rəqəmlər bir evin qarşı-qarşıya duran iki küncünün (x_1, y_1) və (x_2, y_2) koordinatlarıdır. Bütün koordinatların modulu -dan çox deyil. Bütün girişdəki ədədlər tam ədədlərdir.
Lazım olan minimum router sayını və ya həll mümkün deyilsə -1 çıxarın.
Nümunə 1