Силициумска Долина
Во Скопје, се планира изградба на "Македонска Силициумска Долина". На оваа локација, се очекува да инвестираат и да почнат со работа дел од најдобрите фирми за развој на софтвер во светот. Овие фирми сакаат да ги вработат најдобрите информатичари во земјата - што, се разбира, се оние кои што освојуваат медали на натпреварите по информатика организирани од страна на ЗИМ.
Планирано е изгледот на парцелата на која ќе се гради "Македонската Силициумска Долина" да е во вид на правоаголен многуаголник, на кој сите страни му се паралелни со координатните оски од мапата која е дел од урбанистичкиот план на град Скопје. Значи неговите страни меѓусебно се или паралелни или нормални. Така, може да разликуваме "хоризонтални" и "вертикални" страни.
Коле, кој е вработен во град Скопје, е задолжен за изработка на изгледот на парцелата. Тој, од страна на неговите претпоставени, има добиено листа од неколку однапред изградени вертикални огради, и му е дадена наредба да направи правоаголен многуаголник со најголем можен број на страни - користејќи дел од вертикалните огради кои му се дадени (одбраните мора да ги искористи во целост како вертикални страни), и впишувајќи на мапата произволен број на хоризонтални огради. Не е дозволено додавање на дополнителни вертикални огради или преместување (менување на локацијата) на постоечките. Колкав е максималниот број на страни кои може да ги има многуаголникот?
Многуаголникот мора да е поврзан, да нема две страни кои се сечат помеѓу себе, и да има единствена граница.
Влез
Во првата линија е запишан еден цел број N (2 <= N <= 16), кој го означува бројот на вертикални огради. Во секоја од следните N линии се запишани по три цели броја Xi, Y1i и Y2i (0 <= Xi, Y1i, Y2i <= 2000), кои означуваат дека постои вертикална ограда на отсечката помеѓу точките (Xi, Y1i) и (Xi, Y2i). Секогаш ќе важи дека Y1i <> Y2i. Нема да постојат огради кои се допираат или сечат.
Забелешка: Во тест случаи кои ќе носат најмалку 20% од поените, ќе важи (2 <= N <= 3).
Излез
Отпечатете го бараниот максимален број на страни. Доколку не може да се состави правоаголен многуаголник, отпечатете -1.
Ограничувања
Временско ограничување: 2 seconds
Мемориско ограничување: 64 megabytes
Примери
влез 3 0 5 8 3 5 8 3 9 17 | излез 4 |
влез 3 0 0 5 2 0 2 6 2 5 | излез 6 |
влез 2 1 19 15 4 12 19 | излез -1 |
Објаснување за првиот пример: Може да се искористат првите две огради за да се направи квадрат. Квадратот има четири страни, па на излез се печати 4.