Вычисление сложности программы

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

Пока Аня еще только учится, поэтому все программы выглядят как последовательность вложенных циклов, причем все циклы выполняются от некоторого числа или переменной до некоторого другого числа. Ей требуется найти, сколько раз будет выполнена операция внутри самого вложенного цикла. Для этого она создала счетчик, проинициализировала его нулем, и увеличивает его на единицу каждый раз, входя в самый вложенный цикл.

Заметьте, что Аня пока не знает, что в качестве верхней границы в цикле может служить переменная. В качестве нижней границы может выступать как переменная, так и фиксированное значение. Если в каком-то цикле левая граница больше, чем правая, то цикл не будет выполняться вообще.

Так как программы у Ани иногда работают очень долго, то она попросила своего друга узнать ответ, когда же и он не смог этого посчитать, она попросила об этом вас. Помогите ей.

Напишите программу, которая находит, какое значение будет в счетчике в конце работы Аниной программы, если счетчик хранился в переменной целого 32-битного беззнакового типа.

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

В первой строке входного файла INPUT.TXT находится число 1 ≤ N ≤ 3 000 - количество циклов. Далее в N строках написано по два целых числа в каждой. В (i+1)-й строке входного файла записаны левая и правая граница i-го цикла: L_i и R_i (1-i ≤ L_i ≤ 3 000, 0 ≤ R_i ≤ 3 000). При этом если L_i < 0, то это обозначает, что цикл начинается со значения переменной (-L_i)-го цикла, в противном случае цикл начинается со значения L_i.

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

В выходной файл OUTPUT.TXT выведите значение, которое будет в счетчике в конце работы программы.

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]