#P1070C. Cloud Computing

    ID: 4473 Type: RemoteJudge 3000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>data structuresgreedy*2000

Cloud Computing

No submission language available for this problem.

Description

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.

Input

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

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

Samples

5 7 3
1 4 5 3
1 3 5 2
2 5 10 1

44

7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8

462

4 100 3
3 3 2 5
1 1 3 2
2 4 4 4

64