CF1061D TV Shows

你有 $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$ 取模。

在第一个样例中，最优策略是租用 $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$ 取模。 由 ChatGPT 4.1 翻译