Вы решили посмотреть лучшие моменты некоторого фильма. Ваш плеер имеет две кнопки:
- Посмотреть текущую минуту фильма. В результате нажатия этой кнопки вы успешно просматриваете текущую минуту фильма и плеер автоматически переходит к следующей минуте фильма.
- Пропустить ровно x минут фильма (x — некоторое фиксированное положительное целое число). Если плеер сейчас находится на t-й минуте фильма, тогда в результате нажатия этой кнопки (t + x)-я минута станет текущей.
Изначально плеер включен на первой минуте, и вы хотите посмотреть ровно n лучших моментов фильма, причем i-й лучший момент начинается на li минуте и заканчивается на ri минуте (более формально, i-й лучший момент состоит из минут: li, li + 1, ..., ri).
Определите, какое минимальное количество минут фильма вам придется посмотреть, если вы хотите посмотреть все лучшие моменты?
Выходные данные
Выведите единственное число — ответ на задачу.
Примечание
В первом примере плеер изначально включен на первой минуте. Поскольку минуты с 1-й по 4-ю не содержат интересных моментов, мы нажимаем на вторую кнопку. После этого, мы не можем нажать на вторую кнопку и пропустить 3 минуты, поскольку часть из них содержат интересные моменты. Поэтому мы смотрим фильм с 4-й по 6-ю минуты, после этого текущее время равно 7. Аналогично мы снова пропускаем 3 минуты и после этого просматриваем фильм с 10-й по 12-ю минуты. Итого всего мы посмотрим 6 минут фильма.
Во втором примере фильм очень интересный, поэтому придется посмотреть все 100000 минут фильма.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
5 6
10 12
|
6
|
|
2
|
1 1
1 100000
|
100000
|