Задача DVD

У Пети появилась новая компьютерная игра. Друзья, узнав об этом, принесли Пете чистые  DVD диски и попросили переписать игру, чем он и занялся, пообещав, что все будет готово через M + 1 секунд. Но как только Петя начал запись первого диска, он вспомнил, что в его доме сейчас идут ремонтные работы, в связи с которыми будут происходить отключения электричества, поэтому он может и не успеть записать игру на все диски. Так как друзья Пети знают, что он очень ответственный, то они обидятся, если он не успеет завершить работу вовремя.
Игра полностью занимает свободное место на одной DVD-болванке. Привод Пети марки StrangeDVD поддерживает запись на скоростях 4X, 8X и 16X и имеет одну странную особенность: величина X имеет значение, отличное от общепринятого стандарта, поэтому скорости 4X в приводе StrangeDVD и любом другом могут и не совпасть. Будем считать, что лоток привода выдвигается и задвигается мгновенно, и вынимает диск из привода и вставляет диск в привод Петя тоже мгновенно, то есть время тратится только непосредственно на запись очередной копии игры. Привод StrangeDVD не поддерживает мультисессию, поэтому запись на диск производится непрерывно.
При записи на скорости 16X значение качества записанного диска равняется 1, на скорости 8Х — равняется 2, на скорости 4Х — равняется 3. Нужно узнать, сколько времени потратит Петя на запись дисков при условии, что суммарное качество дисков будет максимальным из возможных, а если таких вариантов несколько, то найти такой, при котором затраченное время минимально.
Отключения электричества, как у нас водится,  не согласованы между работающими бригадами, и они могут накладываться на друг друга. В случае, если в данный момент электричество отключено, а другая бригада планировала в этот момент его отключить, то, естественно, она этого не делает.  То есть, если запланировано три отключения электричества:  с 1 по 10  секунду, с 5-ой  по 20-ю и с 15-ой по 30-ую, на В начале 1-ой секунды отключили электричество, на 5-ой  ничего не произойдет, так как электричество уже отключено, на начало 11-ой электричество включат, на конец 15-ой отключат, на начало 31-ой включат. Никакие две бригады не отключают электричество одновременно. Отсчёт времени производится с нулевой секунды. Всего M + 1 секунд  (0, 1, ..., M).
Технические условия. Программа читает с клавиатуры число M (номер последней из имеющихся у Пети секунд), N — количество дисков, которые нужно записать, Q — время в секундах для записи одной копии на скорости 16Х (соответственно для скорости 8Х это время будет равняться 2Q, для скорости 4Х — время 4Q),  K — количество отключений электричества. Далее идут K пар чисел P1, P2 - начало и конец отключения (номера секунд). Эти пары чисел не обязательно расположены в хронологическом порядке, но всегда P1≤ P2. Все числа разделены пробелами.

0≤M, N, P1_і,P2_і≤2 000 000 000
1≤Q≤500 000 000 (или 1≤4Q≤2 000 000 000)
0≤K≤10000
Программа выводит на экран  -1, если Петя не успеет записать все диски. Если успеет, то вывести сначала номер последней секунды, которую Петя потратит на запись и через пробел — суммарное качество, достигнутое при записи.
Пример
Вввод
6 4 1 1 4 5
Вывод
6 5

Комментарий к примеру
У нас семь секунд: 0, 1, 2, 3, 4, 5, 6. Секунды 4—5 заняты, остаются 0, 1, 2, 3, 6. Есть четыре диска, для записи на скорости 16Х нужна одна секунда. Петя закончит запись на последней, шестой секунде, и суммарное качество будет равно 5.