有 $$$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$$$ 为模打印。