A12248 | Cloud Computing

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.

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.

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