eolymp
Yarışlar

USACO Bronze division

Спасатели (Бронза)

Фермер Джон открыл бассейн для своих коров, полагая, что это поможет им расслабиться и произвести больше молока.

В целях безопасности он нанимает n коров в качестве спасателей, у каждой из которых есть смена, охватывающая некоторый непрерывный промежуток времени в течение дня. Для простоты пул открыт с момента t = 0 до времени t = 1000 ежедневно, поэтому каждую смену можно описать двумя целыми числами, что дает время начала и окончания смены коровы. Например, спасатель, начинающий в момент времени t = 4 и заканчивающийся в момент времени t = 7, охватывает три единицы времени (обратите внимание, что конечные точки - это "точки" во времени).

К сожалению, фермер Джон нанял на 1 спасателя больше, чем у него есть средства для содержания. Учитывая, что он должен уволить ровно одного спасателя, каково максимальное количество времени, которое еще можно покрыть сменами остальных спасателей? Промежуток времени покрывается, если присутствует хотя бы один спасатель.

prb10418.gif

Входные данные

Первая строка содержит чило n (1n100). Каждая из следующих n строк описывает спасателя в виде двух целых чисел в диапазоне от 0 до 1000, задающих начальную и конечную точку смены спасателя. Все такие конечные точки различны. Смены разных спасателей могут совпадать.

Выходные данные

Выведите одно число - максимальное количество времени, которое еще можно покрыть, если фермер Джон уволит 1 спасателя.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
5 9
1 4
3 7
Çıxış verilənləri #1
7
Mənbə 2018 USACO Январь, Бронза