Cloud Computing
Contest: 2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred)
Difficulty rating: 2000
Tags: data structures, greedy

Buber is a Berland technology company that specializes in waste of investor's money. Recently Buber decided to transfer its infrastructure to a cloud. The company decided to rent CPU cores in the cloud for $$$n$$$ consecutive days, which are numbered from $$$1$$$ to $$$n$$$. Buber requires $$$k$$$ CPU cores each day.

The cloud provider offers $$$m$$$ tariff plans, the $$$i$$$-th tariff plan is characterized by the following parameters:

- $$$l_i$$$ and $$$r_i$$$ — the $$$i$$$-th tariff plan is available only on days from $$$l_i$$$ to $$$r_i$$$, inclusive,
- $$$c_i$$$ — the number of cores per day available for rent on the $$$i$$$-th tariff plan,
- $$$p_i$$$ — the price of renting one core per day on the $$$i$$$-th tariff plan.

Buber can arbitrarily share its computing core needs between the tariff plans. Every day Buber can rent an arbitrary number of cores (from 0 to $$$c_i$$$) on each of the available plans. The number of rented cores on a tariff plan can vary arbitrarily from day to day.

Find the minimum amount of money that Buber will pay for its work for $$$n$$$ days from $$$1$$$ to $$$n$$$. If on a day the total number of cores for all available tariff plans is strictly less than $$$k$$$, then this day Buber will have to work on fewer cores (and it rents all the available cores), otherwise Buber rents exactly $$$k$$$ cores this day.

Input format:
The first line of the input contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n,k \le 10^6, 1 \le m \le 2\cdot10^5$$$) — the number of days to analyze, the desired daily number of cores, the number of tariff plans.

The following $$$m$$$ lines contain descriptions of tariff plans, one description per line. Each line contains four integers $$$l_i$$$, $$$r_i$$$, $$$c_i$$$, $$$p_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$1 \le c_i, p_i \le 10^6$$$), where $$$l_i$$$ and $$$r_i$$$ are starting and finishing days of the $$$i$$$-th tariff plan, $$$c_i$$$ — number of cores, $$$p_i$$$ — price of a single core for daily rent on the $$$i$$$-th tariff plan.

Output format:
Print a single integer number — the minimal amount of money that Buber will pay.

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

Example input:
5 7 3
1 4 5 3
1 3 5 2
2 5 10 1

Example output:
44

Example input:
7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8

Example output:
462

Editorial:
Use a greedy approach to solve the problem. Iterate through days from $$$1$$$ to $$$n$$$ and maintain the set of tariff plans which are available in the current day.
Now for each day you should find $$$k$$$ cores to rent which are the cheapest. Let's use a segment tree. Build it upon prices $$$[1, 2, \dots, 10^6]$$$. The segment tree maintains two values:
• in each subtree it maintains the total number of cores (so for range of prices it maintains number of cores),
• in each subtree it maintains the total price of cores (so for range of prices it maintains total price of all cores)
To find total minimum price of $$$k$$$ cores use a top-bottom tree scan: go to the left subtree (if it contains at least $$$k$$$ cores) or take the whole left subtree and go to the right to find the rest of cores.
Also to maintain a segment tree while iteration from day to day, just use two types of events: new $$$с_i$$$ cores with the price $$$p_i$$$ added, new $$$с_i$$$ cores with the price $$$p_i$$$ removed. Actually, it is just typical increment/decrement operation in a single point of a segment tree.