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:
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.