Artemida
Zeus, vəhşi təbiətin ilahəsi Artemidaya meşə yaratmaq üçün düzbucaqlı bir sahə ayırdı. Bu sahənin sol tərəfi OY oxunun müsbət hissəsinə, alt tərəfi isə OX oxunun müsbət hissəsinə uyğun gəlir və (0, 0) nöqtəsi sahənin sol alt küncünə uyğundur. Zeus, Artemidanın yalnız koordinatları tam olan nöqtələrdə ağac yetişdirməsini istədi. Artemida isə meşənin təbii görünüşünü sevdiyi üçün ağacları elə əkirdi ki, istənilən iki ağacı birləşdirən xətt OX və OY oxlarına paralel olmasın.
Bir gün Zeus, Artemidadan aşağıdakı qaydalara əməl edərək ağacları kəsməsini istədi:
Zeus ən az T ağacın kəsilməsini tələb edir.
Gələcək futbol qələbələri üçün düzbucaqlı futbol meydançası əldə etmək məqsədilə Artemida müəyyən bir düzbucaqlı sahənin içindəki bütün ağacları kəsməli və sahənin xaricində heç bir ağacı kəsməməlidir.
Bu düzbucaqlı sahənin tərəfləri OX və OY oxlarına paralel olmalıdır.
Sahənin iki əks küncü ağacların yerləşdiyi yerlərdə olmalıdır, buna görə də bu ağaclar da kəsilməlidir.
Artemida ağacları sevdiyi üçün şərtləri yerinə yetirərkən mümkün qədər az ağac kəsmək istəyir. Siz, Artemidaya ağacların meşədə yerləşməsi və kəsilməsi lazım olan minimum ağac sayı T haqqında məlumat verərək, ağacların kəsilməsi üçün sahəni seçən bir proqram yazmalısınız.
Giriş verilənləri
Giriş faylının ilk sətiri meşədəki ağacların sayını göstərən bir tam ədəd N ehtiva edir. İkinci sətir kəsilməsi lazım olan minimum ağac sayını göstərən bir tam ədəd T ehtiva edir. Növbəti N sətir N ağacın yerini təsvir edir. Bu sətirlərin hər biri iki tam ədəd ehtiva edir: əvvəlcə ağacın X-koordinatı, sonra isə Y-koordinatı.
Bütün testlər üçün 1 < N ≤ 20000, 0 ≤ X, Y ≤ 64000 və 1 < T ≤ N. 50% testlər üçün: 1 < N < 5000.
Çıxış verilənləri
Çıxış faylı bir sətirdə bir boşluqla ayrılmış iki tam ədəd I və J ehtiva etməlidir. Artemida giriş faylının I+2-ci sətirində verilmiş koordinatlarla I-ci ağacı və J+2-ci sətirində verilmiş koordinatlarla J-ci ağacı ağacların kəsilməsi sahəsinin küncləri kimi nəzərə almalıdır. Bu iki ədədin çıxışdakı sırası əhəmiyyətli deyil. Belə bir ağac cütünü seçmək üçün bir neçə variant varsa, yalnız birini tapıb çıxarmalısınız. Bütün testlər üçün ən azı bir həll mövcuddur.