Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить k
досок забора. При этом Том может в любой момент вернуться за краской к цистерне.
Изначально Том находится у цистерны. Соседние доски находятся на расстоянии 1 фута друг от друга, цистерна находится на расстоянии 1 фута от первой доски. По окончании работы Том должен положить кисточку и ведерко на свою исходную позицию рядом с цистерной.
Требуется выяснить, какое минимальное расстояние Тому необходимо пройти, чтобы покрасить забор.
Входные данные
Первая строка содержит количество досок в заборе n (1 ≤ n ≤ 10
9) и вместимость ведерка k (1 ≤ k ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора m (1 ≤ m ≤ 50).
Далее следуют m строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей li и правой границей ri (1 ≤ l
i ≤ r
i ≤ n). Такое описание означает, что не покрашены l
i-я, (l
i+1)-я, …, (r
i–1)-я, r
i-я доски забора (доски нумеруются от 1 до n). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.
Выходные данные
Выведите одно число — минимальное расстояние в футах, которое необходимо пройти Тому для выполнения своего ответственного задания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
2
1 2
5 5
|
12
|