28975번 - Волшебные существа 다국어

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

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

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

В первой строке входного файла заданы числа $t$ и $s$ --- момент времени, когда первый питомец покинул чемодан, и интервал времени между побегами питомцев соответственно ($0 \le t \le 10^{12}$, $1 \le s \le 10^{12}$).

Во второй строке содержится число $n$ --- количество интересующих Саламандера отрезков времени ($1 \le n \le 100\, 000$). В следующих $n$ строках содержатся числа $a_i, b_i$ --- левая и правая границы $i$-го отрезка времени ($0 \le a_i, b_i \le 10^{12}$).

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

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