D. Телепередачи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ телепередач, которые вы хотите посмотреть. Предположим, что всё время разбито на равные отрезки называемые «минутами». Тогда $$$i$$$-я телепередача идёт с $$$l_i$$$-й по $$$r_i$$$-ю минуту, оба конца включительно.

Конечно, чтобы посмотреть телепередачу нужен телевизор, а также нельзя смотреть две телепередачи идущие одновременно на одном телевизоре. Из-за этого, возможно, в некоторые минуты вам понадобится более одного телевизора. В частности, если отрезки $$$[l_i, r_i]$$$ и $$$[l_j, r_j]$$$ пересекаются, то телепередачи $$$i$$$ и $$$j$$$ нельзя смотреть одновременно на одном телевизоре.

После того как вы начали смотреть какую-то телепередачу на каком-то телевизоре её нельзя «переместить» на другой телевизор (это было бы слишком отвлекающим действием), а также нельзя начать смотреть другую телепередачу на том же телевизоре пока эта телепередача не закончится.

К счастью, рядом с вами есть магазин по аренде телевизоров. Он сдаёт телевизор в аренду за $$$x$$$ рупий и взимает $$$y$$$ ($$$y < x$$$) рупий за каждую следующую минуту, в течении которой вы держите телевизор у себя. В частности, чтобы арендовать один телевизор на время $$$[a; b]$$$ нужно заплатить $$$x + y \cdot (b - a)$$$ рупий.

Считайте, что аренда и возврат телевизора не занимает времени и не отвлекает от просмотра других телепередач. Выясните минимальное возможное количество денег, которое нужно заплатить, чтобы посмотреть все телепередачи. Так как это значение может быть достаточно велико, выведите его по модулю $$$10^9 + 7$$$.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$x$$$ и $$$y$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le y < x \le 10^9$$$) — количество телепередач, стоимость аренды телевизора в первую минуту и cтоимость аренды телевизора в каждую последующую минуту.

Каждая из следующих $$$n$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$), обозначающие начальную и конечную минуту $$$i$$$-й телепередачи.

Выходные данные

Выведите одно целое число — минимальную стоимость просмотра всех телепередач, взятую по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
5 4 3
1 2
4 10
2 4
10 11
5 9
Выходные данные
60
Входные данные
6 3 2
8 20
6 22
4 15
20 28
17 25
20 27
Выходные данные
142
Входные данные
2 1000000000 2
1 2
2 3
Выходные данные
999999997
Примечание

В первом примере оптимально арендовать $$$3$$$ телевизора и посмотреть:

  • Телепередачу $$$[1, 2]$$$ на первом телевизоре,
  • Телепередачу $$$[4, 10]$$$ на втором телевизоре,
  • Тепередачи $$$[2, 4], [5, 9], [10, 11]$$$ на третьем телевизоре.

Таким образом, стоимость аренды первого телевизора равна $$$4 + 3 \cdot (2 - 1) = 7$$$, второго $$$4 + 3 \cdot (10 - 4) = 22$$$ и треьего $$$4 + 3 \cdot (11 - 2) = 31$$$, что в сумме составляет $$$60$$$ рупий.

Во втором примере оптимально посмотреть каждую телепередачу на отдельном телевизоре.

В третьем примере тоже оптимально посмотреть каждую телепередачу на отдельном телевизоре. Обратите внимание, что ответ нужно вывести по модулю $$$10^9 + 7$$$.