TV Shows
Contest: Codeforces Round 523 (Div. 2)
Difficulty rating: 2000
Tags: data structures, greedy, implementation, sortings

There are $$$n$$$ TV shows you want to watch. Suppose the whole time is split into equal parts called "minutes". The $$$i$$$-th of the shows is going from $$$l_i$$$-th to $$$r_i$$$-th minute, both ends inclusive.

You need a TV to watch a TV show and you can't watch two TV shows which air at the same time on the same TV, so it is possible you will need multiple TVs in some minutes. For example, if segments $$$[l_i, r_i]$$$ and $$$[l_j, r_j]$$$ intersect, then shows $$$i$$$ and $$$j$$$ can't be watched simultaneously on one TV.

Once you start watching a show on some TV it is not possible to "move" it to another TV (since it would be too distracting), or to watch another show on the same TV until this show ends.

There is a TV Rental shop near you. It rents a TV for $$$x$$$ rupees, and charges $$$y$$$ ($$$y < x$$$) rupees for every extra minute you keep the TV. So in order to rent a TV for minutes $$$[a; b]$$$ you will need to pay $$$x + y \cdot (b - a)$$$.

You can assume, that taking and returning of the TV doesn't take any time and doesn't distract from watching other TV shows. Find the minimum possible cost to view all shows. Since this value could be too large, print it modulo $$$10^9 + 7$$$.

Input format:
The first line contains integers $$$n$$$, $$$x$$$ and $$$y$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le y < x \le 10^9$$$) — the number of TV shows, the cost to rent a TV for the first minute and the cost to rent a TV for every subsequent minute.

Each of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$) denoting the start and the end minute of the $$$i$$$-th TV show.

Output format:
Print exactly one integer — the minimum cost to view all the shows taken modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the optimal strategy would be to rent $$$3$$$ TVs to watch:

- Show $$$[1, 2]$$$ on the first TV,
- Show $$$[4, 10]$$$ on the second TV,
- Shows $$$[2, 4], [5, 9], [10, 11]$$$ on the third TV.

This way the cost for the first TV is $$$4 + 3 \cdot (2 - 1) = 7$$$, for the second is $$$4 + 3 \cdot (10 - 4) = 22$$$ and for the third is $$$4 + 3 \cdot (11 - 2) = 31$$$, which gives $$$60$$$ int total.

In the second example, it is optimal watch each show on a new TV.

In third example, it is optimal to watch both shows on a new TV. Note that the answer is to be printed modulo $$$10^9 + 7$$$.

Example input:
5 4 3
1 2
4 10
2 4
10 11
5 9

Example output:
60

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

Example output:
142

Editorial:
Solution: Sort the TV shows on the basis of their starting time. Now, we start allocating TVs greedily to the shows. For any show $$$i$$$, we allocate a new TV only if there is no old TV where the show ends at $$$r_o$$$, such that $$$r_o < l_i$$$ and $$$(l_i - r_o) \cdot y <= x$$$. Also, if there are many such old TVs, then we use the TV where $$$r_o$$$ is maximum.
Proof: Notice that there is a minimal cost of $$$\sum_{i=1}^{n} (r_i - l_i) \cdot y$$$, which will always be added. Hence, the optimal solution completely depends on the rent of new TV and the time wasted on old TVs.
Now, lets try to prove that allocating an old TV with maximum $$$r_o$$$ is optimal. Suppose we are allocating a TV to show $$$i$$$. Let's consider two old TVs $$$o1$$$ and $$$o2$$$, such that $$$r_{o1} < r_{o2} < l_i$$$ and $$$(l_i - r_{o1}) \cdot y <= x$$$. In such a case, it is possible to allocate both the TVs to this show. For choosing which TV to be allocated let's consider the three possible cases:
Case I: There is no show $$$j (j > i)$$$, such that $$$(l_j - r_{o2}) \cdot y <= x$$$. In this case, it would be better to allocate TV $$$o2$$$ to show $$$i$$$, since $$$(l_i - r_{o2}) \cdot y < (l_i - r_{o1}) \cdot y$$$. Hence, allocating TV $$$o2$$$ to show $$$i$$$ is optimal in this case.
Case II: There are shows $$$j (j > i)$$$, such that $$$(l_j - r_{o2}) \cdot y <= x$$$; but there is no show $$$j (j > i)$$$, such that $$$(l_j - r_{o1}) \cdot y <= x$$$. In this case, if we allocate TV $$$o1$$$ to show $$$i$$$ and TV $$$o2$$$ to show $$$j$$$, then the cost will be $$$(l_j - r_{o2}) \cdot y + (l_i - r_{o1}) \cdot y$$$. And, if we allocate TV $$$o2$$$ to show $$$i$$$, then we need to buy a new TV for show $$$j$$$ and our cost will be $$$x +(l_i - r_{o2}) \cdot y$$$. Now, as $$$(l_j - r_{o1}) \cdot y > x$$$, $$$(l_j - r_{o2}) \cdot y + (l_i - r_{o1}) \cdot y > x +(l_i - r_{o2}) \cdot y$$$. Hence, allocating TV $$$o2$$$ instead of TV $$$o1$$$ to show $$$i$$$ is optimal in this case.
Case III: There are shows $$$j (j > i)$$$, such that $$$(l_j - r_{o1}) \cdot y <= x$$$. In this case, if we allocate TV $$$o1$$$ to show $$$i$$$, cost will be $$$(l_i - r_{o1}) \cdot y + (l_j - r_{o2}) \cdot y$$$. If we allocate TV $$$o2$$$ to show $$$i$$$, cost will be $$$(l_i - r_{o2}) \cdot y + (l_j - r_{o1}) \cdot y$$$. Here, we can see that in both of the allocations, the cost is $$$(l_i + l_j - r_{o1} - r_{o2}) \cdot y$$$ and so any allocation is optimal here.
Hence, we can see that if more than one old TVs are available, allocating the one with maximum $$$r_o$$$ is always optimal.
Overall Complexity: $$$O(n \cdot \log n)$$$