← 返回题目列表

Codeforces · 1061/D

D. 电视节目

中文机器翻译题面 查看原题

有 $$$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$$$) - 电视节目的数量、第一分钟租用电视的费用以及随后每分钟租用电视的费用。

接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$) 表示第 $$$i$$$ 电视节目的开始和结束分钟。

输出

精确打印一个整数——观看所有节目的最低成本,以 $$$10^9 + 7$$$ 为模。

示例

输入 #1

5 4 3
1 2
4 10
2 4
10 11
5 9

输出 #1

60

输入 #2

6 3 2
8 20
6 22
4 15
20 28
17 25
20 27

输出 #2

142

输入 #3

2 1000000000 2
1 2
2 3

输出 #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$$$ 为模打印。