У вас осталась частичная информация о счете во время исторического футбольного матча. Вам задан набор пар \((a_i, b_i)\), обозначающих, что во время матча на табло был счет «\(a_i\): \(b_i\)». Известно, что если текущий счёт «\(x\):\(y\)», то после гола он сменится на «\(x+1\):\(y\)» или «\(x\):\(y+1\)». Какое наибольшее количество раз на табло могла появиться ничья?
Пары «\(a_i\): \(b_i\)» заданы в хронологическом порядке (увеличения времени), но вам заданы только некоторые моменты времени. Последняя пара обязательно соответствует окончанию матча.
Выходные данные
Выведите наибольшее возможное количество моментов времени в матче, в которое счет становился ничейным. Момент начала матча, в который счет становится 0:0, также считается.
Примечание
В первом примере одна из возможных последовательностей изменения счета с наибольшем количеством ничьих следующая: 0:0, 1:0, 2:0, 2:1, 3:1, 3:2, 3:3, 3:4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 0
3 1
3 4
|
2
|
|
2
|
3
0 0
0 0
0 0
|
1
|
|
3
|
1
5 4
|
5
|