2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Cloud Computing

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBuber 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

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.

Examples

Input

5 7 3

1 4 5 3

1 3 5 2

2 5 10 1

Output

44

Input

7 13 5

2 3 10 7

3 5 10 10

1 2 10 6

4 5 10 9

3 4 10 8

Output

462

Input

4 100 3

3 3 2 5

1 1 3 2

2 4 4 4

Output

64

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/14/2018 15:23:44 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|