У вас осталась частичная информация о счете во время исторического футбольного матча. Вам задан набор пар \((a_i, b_i)\), обозначающих, что во время матча на табло был счет «\(a_i\): \(b_i\)». Известно, что если текущий счёт «\(x\):\(y\)», то после гола он сменится на «\(x+1\):\(y\)» или «\(x\):\(y+1\)». Какое наибольшее количество раз на табло могла появиться ничья?
Пары «\(a_i\): \(b_i\)» заданы в хронологическом порядке (увеличения времени), но вам заданы только некоторые моменты времени. Последняя пара обязательно соответствует окончанию матча.
В первой строке записано целое число \(n\) (\(1 \le n \le 10000\)) — количество сохранившихся записей о счете в матче. В следующих \(n\) строках записано по два целых числа \(a_i\) и \(b_i\) (\(0 \le a_i, b_i \le 10^9\)), обозначающие счет на табло (т.е. число голов, забитых первой командой, и число голов, забитое второй командой). Эти записи перечислены в хронологическом порядке, т.е. последовательности \(x_i\) и \(y_j\) неубывающие. Последняя запись означает финальный счет матча.
Выведите наибольшее возможное количество моментов времени в матче, в которое счет становился ничейным. Момент начала матча, в который счет становится 0:0, также считается.
В первом примере одна из возможных последовательностей изменения счета с наибольшем количеством ничьих следующая: 0:0, 1:0, 2:0, 2:1, 3:1, 3:2, 3:3, 3:4.
3 2 0 3 1 3 4
2
3 0 0 0 0 0 0
1
1 5 4
5
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач