Задача №112774. Кладовка из Простоквашино
Сразу же после заселения в новый дом в Простоквашино кот Матроскин, Шарик и дядя Фёдор затеяли ремонт. Непосредственно перед его началом они обнаружили, что в доме отсутствует кладовка для стройматериалов, и наспех пристроили её к дому. Как только вспомогательное строение было готово, встал вопрос о необходимости провести туда электричество и повесить лампочку.
Обсудив вопросы электрификации новых помещений с почтальоном Печкиным, наши герои узнали много полезной информации. Чтобы посетители не мучились с выбором, в деревенском магазине продаётся только один вид лампочек, зато в неограниченных количествах. Стоит одна лампочка ни дорого, ни дёшево, а ровно \(C\) рублей. Правда, лампочки в магазине не самые качественные, и включить каждую из них можно только \(K\) раз, а на \(K\) + 1 включение она перегорает. Недостаток этот компенсируется тем, что во включенном состоянии лампочка перегореть не может. К сожалению, электроэнергия в Простоквашино недешевая, и каждая минута работы лампочки обойдется дяде Фёдору и его друзьям в \(D\) рублей.
Узнав всё это, экономный Матроскин составил поминутный график из \(N\) предполагаемых посещений кладовки. Каждый визит в новое помещение задаётся моментом входа \(a_i\) и моментом выхода \(b_i\). Таким образом, \(i\)-й визит продолжается ровно \(b_i − a_i\) минут.
Разумеется, во время посещения свет в кладовке должен быть включён. Если в начале очередного визита лампочка не горит, то посетитель сразу её включает, а вот уходя он может как выключить свет, так и оставить его включенным. Если во время очередного включения лампочка перегорает, то её приходится немедленно заменить. Теперь Матроскина интересует минимальное количество рублей, которое придётся потратить, чтобы выполнить все запланированные визиты в кладовку. Изначально в помещении уже висит новая лампочка в выключенном состоянии.
В первой строке входных данных записаны четыре целых числа \(N\), \(K\), \(C\), \(D\) — количество планируемых посещений кладовки, количество успешных включений для одной лампочки, стоимость покупки лампочки и стоимость минуты работы лампочки соответственно (\(1 \le N, K \le 200 000, 1 \le C, D \le 10^9\)).
В следующих \(N\) строках даны по два целых положительных числа \(a_i\) и \(b_i\), описывающих предполагаемые визиты в кладовку (\(1 \le a_i < b_i \le 10^9\)). Посещения не пересекаются по времени и упорядочены, то есть \(b_i < a_{i+1}\).
Выведите одно целое число — минимальное количество рублей, которое придётся потратить жителям дома, чтобы выполнить все запланированные визиты в кладовку при свете.
В первом примере достаточно заплатить только за электроэнергию: лампочка должна быть включена на третьей минуте и выключена на пятой, стало быть, суммарные затраты составляют (5 − 3) × 6 = 12
Во втором примере выгодно не выключать лампочку между первым и вторым посетителем, а для третьего использовать уже новую лампочку.
Тесты к этой задаче состоят из пяти групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
1 2 5 6 3 5
12
3 1 15 10 1 3 4 5 30 35
105