Областная олимпиада по информатике. 10-11 классы. 2014-2015 учебный год.


Есеп D. Мұз айдыны

Ограничение по времени:
2 секунды
Ограничение по памяти:
64 мегабайта

Андрей мұз айдынында сырғанауды жақсы көргенi соншама, қысқы демалыста оны кез келген күнi сол жерде кездестiрүге болатын. Сол үшiн, оның достарының жаңа жылды мұз алаңында тойлау шешiмiн ол қуанышпен қарсалды. Бiрақ ата-аналар балаларын кешке дейiн жiберуге бiр шарт қойды — әрқайсысы өзiмен бiрге қарындасын алып бару керек.
Балалар мұз алаңында жұптасып билейди екен. Мұз айдынына $N$ бала барады (Андреймен бiрге), әрқайсысы өзiмен бiрге бiр қарындасын алып келедi. Ұлдар тек қана қыздармен билегiсi келедi. Қыздар да тек қана ұлдармен жұптасқанды қалайды. Соның үстiнен, қыздар өзiнен биiк ұлдарды ғана менсiнедi екен. Соңғы шарт — жiгiттер өзiнiң қарындасымен билеуге уялғаннан, аға мен қарындас бiр жұпта болалмайды.
Берiлген ұлдармен қыздардын бойларына қарап, қанша барынша көп жұп қурастыруға болатынын табыңыз.
Формат входного файла
Кiру файлдың бiрiншi жолында жалғыз $N$ саны берiлген — қанша ұл бар екенi. Келесi $N$ жолдын әрқайсында екi бүтiн сан — ұлдың бойы және оның қарындасының бойы берiлген. Берiлген сандардың барлығы $10^5$-нен аспайды.
Формат выходного файла
Шығу файлына тек бiр сан шығарыныз — есептiң жауабы, яғни максималды қанша жұп мұз айдынына бiр уақытта шыға алады
Примеры:
Вход
5
1 2
5 2
2 1
3 3
5 1
Ответ
4
Вход
5
2 2
1 2
2 1
1 2
4 4
Ответ
2
Вход
5
3 2
4 5
3 3
1 4
1 4
Ответ
2
Замечание
$N \le 500$ — $30\%$ тест үшiн.
посмотреть в олимпиаде

Комментарий/решение: