Schedule
Турнир за Купата на Декана, 2009
Time Limit: 0.1s, Memory Limit: 64MiB
"Тук нещо не е наред." – каза Ели на Крис, гледайки плана им за деня. Той се състоеше от най-различни неща, като например фризьор, шопинг, кино, маникюр и т.н. – описани с час, който са запазили и час, в който съответното занятие ще свърши. Те осъзнаха, че дори да си разпределят оптимално коя къде да ходи, отново е възможно да няма практически начин да посетят всички мероприятия. От друга страна, като истински фенове на ефективността, те се питат колко ли най-много различни неща могат да бъдат посетени от поне една от тях. Разбира се, по всяко време всяка от тях може да бъде на най-много едно място.
Вход
На първия ред на стандартния вход ще бъде зададено цялото число N – броят неща в техния списък. Всеки от следващите N реда се състои от две цели числа – Ai и Bi – съответно времето, в което занятието започва, и времето, в което свършва. Приемете, че пътят е пренебрежимо кратък (все пак Ели има Вейрон =)) и, например, ако фризьорът свършва в минутата, когато киното започва, те могат да го посетят.
Изход
На единствен ред на стандартния изход отпечатайте колко най-много различни мероприятия могат да бъдат посетени от поне едно от момичетата.
Ограничения
  • 1 ≤ N ≤ 20
  • 0 ≤ Ai < Bi ≤ 1,000
Примерен Вход Примерен Изход
8 0 3 0 5 3 6 6 8 10 14 9 16 12 13 13 15 7
Ако Ели посети занятия 1, 3, 4 и 5, а Крис – 2, 4, 7 и 8 те ще успеят да посетят седем от осемте неща в техния списък. Забележете, че и Ели и Крис посещават 4, но тъй като ни интересуват само различните мероприятия, то не се брои два пъти към отговора. За съжаление те трябва да се лишат от поне едно от заниманията, тъй като има три по едно и също време.
Мрън!