Есть \(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\).
Примечание
В первом примере оптимально арендовать \(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\).