Задача
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.