Рабочее место участника

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

Гигамеш умеет прыгать на фиксированное расстояние `L` вперед и назад. Прыжки можно делать только в точках с целыми координатами. Также Гигамеш может передвигаться пешком по земле и облакам. Небольшая ошибка в параметре прочности не сделала облака достаточно надежной конструкцией, поэтому Гигамеш должен был при переправе минимизировать расстояние, пройденное по облакам пешком.

Напишите программу, которая определит по расположению облаков минимальное расстояние, которое должен пройти Гигамеш пешком по облакам, чтобы переправиться на другой край пропасти.

Первая строка ввода содержит три целых числа: ширина пропасти `W`, длина прыжка `L` (`2\ ≤\ L\ ≤\ 1000`, `L < W ≤\ 100 000`) и количество облаков `N` (`1\ ≤\ N\ ≤\ 10 000`). Далее следует `N` строк, каждая строка содержит два целых числа `a_i` и `b_i` — координаты начала и окончания поверхности `i`-го облака (`0\ <\ a_1\ ≤\ L`, `a_i\ <\ b_i`, `b_i\ <\ a_{i+1}`, `a_{i+1} - b_i ≤\ L`, `b_N <\ W`, `W - b_N\ ≤\ L`, координата 0 соответствует краю пропасти, на котором стоит Гигамеш). Первый прыжок можно сделать как из точки на краю разлома, так и находящейся на некотором расстоянии от него, аналогично для приземления на другой стороне разлома (см. пример ввода 2).

В первой строке вывести одно целое число — минимальное расстояние, которое должен пройти Гигамеш пешком по облакам при переправе. Во второй строке вывести координаты точек, в которых Гигамеш должен делать прыжки. Можно вывести любой вариант, в котором достигается найденный минимум. Если переправиться на другой край пропасти невозможно, то в первой строке вывести число `-1`.

17 5 4
4 5
6 8
9 11
12 13

2
0 5 11 7 12

5 4 1
2 3

0
-2 2