시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB197633.333%

문제

Том Сойер получил важное задание по покраске забора. Забор состоит из n досок. Он когда-то был покрашен, однако с некоторых участков забора краска облупилась. Эти доски Тому и необходимо покрасить. Так как забор большой, пришлось подвезти к забору целую цистерну с краской. Цистерна была помещена у края забора и не может перемещаться. У Тома есть ведерко, набрав краски в которое, Том может покрасить k досок забора. При этом Том может в любой момент вернуться за краской к цистерне. 

Изначально Том находится у цистерны. Соседние доски находятся на расстоянии 1 фута друг от друга, цистерна находится на расстоянии 1 фута от первой доски. По окончании работы Том должен положить кисточку и ведерко на свою исходную позицию рядом с цистерной. 

Требуется выяснить, какое минимальное расстояние Тому необходимо пройти, чтобы покрасить забор.

입력

Первая строка входного файла содержит количество досок в заборе n (1 ≤ n ≤ 109) и вместимость ведерка k (1 ≤ k ≤ 100). Во второй строке содержится количество неокрашенных отрезков забора m (1 ≤ m ≤ 50). Далее следуют m строк, в каждой из которых описан один неокрашенный отрезок. Отрезок описывается своей левой границей li и правой границей ri (1 ≤ li ≤ ri ≤ n). Такое описание означает, что не покрашены li-я, (li+1)-я, …, (ri–1)-я, ri-я доски забора (доски нумеруются от 1 до n). Гарантируется, что неокрашенные отрезки, заданные во входном файле, не пересекаются.

출력

Выведите одно число — минимальное расстояние в футах, которое необходимо пройти Тому для выполнения своего ответственного задания. 

예제 입력 1

10 2
2
8 10
3 5

예제 출력 1

44

예제 입력 2

15 5
3
2 4
6 8
10 12

예제 출력 2

36

힌트