Волшебные существа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
beasts.in
вывод
beasts.out

Как известно, у одного из самых известных магозоологов Великобритании Ньюта Саламандера имеется волшебный чемодан. На чемодан Ньют наложил Заклинание незримого расширения, а внутри него хранил обширную коллекцию редких, находящихся под угрозой исчезновения волшебных существ, найденных им во время кругосветных путешествий.

Однажды Ньют оставил свой чемодан полуоткрытым, и существа решили совершить побег. Однако сделать это одновременно они не могут, так как створки чемодана очень узкие. Время, необходимое каждому питомцу для того, чтобы вылезти из чемодана , составляет s. Первый из питомцев покидает чемодан в момент времени t, а последующие — в моменты времени t + s, t + 2·s и так далее.

Ньют Саламандер слишком поздно узнал о хитром плане питомцев, и сейчас его интересует, какое суммарное количество существ сбежало из чемодана в промежутки времени [ai, bi], включая границы. Питомцев в волшебном чемодане содержится бесконечное количество.

Входные данные

В первой строке входного файла заданы числа t и s — момент времени, когда первый питомец покинул чемодан, и интервал времени между побегами питомцев соответственно (0 ≤ t ≤ 1012, 1 ≤ s ≤ 1012).

Во второй строке содержится число n — количество интересующих Саламандера отрезков времени (1 ≤ n ≤ 100 000). В следующих n строках содержатся числа ai, bi — левая и правая границы i-го отрезка времени (0 ≤ ai, bi ≤ 1012).

Выходные данные

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

Примеры

Входные данные
4 3
2
1 3
5 13
Выходные данные
3
Входные данные
1 10
3
1 1
1 1
1 1
Выходные данные
3

Примечание

В первом тесте из условия существа сбегают в моменты времени 7, 10 и 13, принадлежащие второму промежутку времени. Во время первого промежутка ни одно существо не совершает побег.