e-olymp
Змагання

жадібний алгоритм

Прийом у директора

Секретар загальноосвітнього закладу Марта Георгіївна щоденно починала свій робочий день з претензій до директора:

  • Ось Ви, Іван Іванович, заступнику з навчальної частини програму для складання розкладу уже придбали. А що мені робити? Адже мені потрібно згідно Ваших вимог скласти графік прийому відвідувачів, а програму для планування роботи адміністрації Ви мені не придбали...

Спробуйте допомогти секретарю у її роботі. Для цього вам потрібно організувати прийом відвідувачів на підставі побажань, зроблених ними у відповідній книзі у секретаря.

Прийом двох відвідувачів одночасно заборонений. У момент закінчення прийому одного відвідувача може розпочатись прийом іншого - вони зустрілись у дверях кабінету.

Вхідні дані

У першому рядку міститься число n (n1000) - кількість працівників та відвідувачів, що записались на прийом. У наступних n рядках задано по два числа T1i - час початку зустрічі з директором та через пропуск T2i - час його закінчення у форматі hh:mm. Відомо, що час задано на протязі однієї доби, всі T2iT1i.

Вихідні дані

Вивести максимальну кількість відвідувачів, яку зможе прийняти директор школи протягом робочого дня.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4
09:10 13:05
14:25 14:30
14:20 15:15
15:00 17:00
Вихідні дані #1
3