Ferm 2
Fermada bir təsərrüfat var. Fermer burada oturub, nə qədər heyvanı olduğunu hesablayır. O, dəvələr, qoyunlar və yaşıl tarakanlar yetişdirir. Fermada yeni bir heyvan doğulduqda, onun hansı heyvan olduğunu müəyyən etmək lazımdır. Fermer tarakanları digər heyvanlardan ayırd edə bilir, amma dəvə və ya qoyun olduğunu müəyyən etmək üçün ekspert komissiyasına müraciət edir. Komissiya yeni doğulmuş heyvanın hündürlüyü və buynuz uzunluğunu ölçür. Bu məlumatlara əsasən, heyvanın hansı qrupa (dəvə və ya qoyun) aid olduğunu müəyyən edirlər.
Ekspertlər belə hərəkət edirlər: komissiya çağırıldıqdan sonra i-ci ekspert 2 tam ədəd a_i və b_i seçir, bu ədədlər modul üzrə 2∙10^9-dan çox olmamalıdır. Yeni doğulmuş heyvanın parametrləri (A, B) olduqda, ekspert (a_iA + b_iB) ifadəsini hesablayır. Əgər ifadə müsbətdirsə, ekspert heyvanın dəvə olduğunu düşünür, əgər mənfidirsə, qoyun olduğunu düşünür. Əgər ifadə 0-a bərabərdirsə, ekspert qərarsız qalır və heç bir mühakimə yürütmür.
Komissiya konkret bir heyvan haqqında qərarını səsvermə yolu ilə qəbul edir. Əgər ekspertlərin yarısından çoxu heyvanın dəvə olduğunu düşünürsə, komissiya fermerə təsərrüfatda bir dəvə daha olduğunu bildirir. Əgər ekspertlərin yarısından çoxu heyvanın qoyun olduğunu düşünürsə, kitabda yeni doğulmuş qoyun qeyd edilir. Əgər komissiya heyvanı nə dəvə, nə də qoyun kimi tanıya bilmirsə, fermer yaşıl tarakan doğulduğunu düşünür.
Bir gün fermer qərara gəldi ki, bu qədər eksperti işə götürmək baha başa gəlir. Həqiqətən də, məsələn, komissiya 4 ekspertdən ibarətdirsə və bütün məsələlərdə birinci ekspert üçüncü ilə, ikinci isə dördüncü ilə razılaşırsa, üçüncü və dördüncü ekspertləri işdən çıxarmaq olar, komissiyanın iş keyfiyyətini itirmədən. Fermada artıq N dəvə və qoyun var (hər biri haqqında dəvə və ya qoyun olduğu məlumdur). Fermer elə minimal K tapmaq istəyir ki, K ekspertdən ibarət komissiya bütün dəvələri dəvə, qoyunları isə qoyun kimi tanıya bilsin (yəni hər bir ekspert a_i və b_i ədədlərini seçə bilsin).
Giriş verilənləri
Girişin ilk sətirində təsərrüfatdakı dəvə və qoyunların ümumi sayı olan N ədədi verilir (1 ≤ N ≤ 10000). Sonra N sətir var, hər birində j-ci heyvanın parametrləri olan 3 tam ədəd verilir: A_j — hörgü hündürlüyü, B_j — buynuz uzunluğu və C_j (1, əgər heyvan dəvədirsə, və 2, əgər qoyundursa). 0 ≤ A_j, B_j ≤ 10000.
Çıxış verilənləri
Əgər fermerin tələblərinə cavab verən komissiya mövcud deyilsə, –1 ədədini çıxarın. Əks halda, ilk sətirdə axtarılan K ədədini çıxarın. Növbəti K sətirdə ekspertlərin qərar qəbul edərkən istifadə edə biləcəyi a_i və b_i ədədlərini boşluqla ayıraraq çıxarın. Ekspert komissiyası bu ədədlərlə silahlanaraq hər bir N heyvanı haqqında düzgün qərar qəbul edə bilsə, istənilən əmsalları çıxara bilərsiniz.