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

Buber 是一家位于 Berland 的科技公司，专长于挥霍投资者的资金。最近，Buber 决定将其基础设施迁移至云平台。该公司计划在连续 $n$ 天（编号从 $1$ 到 $n$）内租用 CPU 核心。Buber 每天需要 $k$ 个 CPU 核心。

云服务提供商提供了 $m$ 种计费方案，其中第 $i$ 种计费方案具有如下参数：

• $l_i$ 和 $r_i$ —— 第 $i$ 种计费方案仅在第 $l_i$ 天至第 $r_i$ 天（含端点）期间可用；
• $c_i$ —— 在第 $i$ 种计费方案下，每天最多可租用的 CPU 核心数；
• $p_i$ —— 在第 $i$ 种计费方案下，租用一个 CPU 核心一天的价格。

Buber 可以在不同计费方案之间任意分配其所需的计算核心数。每天，Buber 可在每种当天可用的计费方案中租用任意数量的核心（从 $0$ 到 $c_i$）。同一种计费方案下每天租用的核心数可以任意变化。

求 Buber 在第 $1$ 天至第 $n$ 天这 $n$ 天内所需支付的最少总金额。若某天所有可用计费方案所能提供的核心总数严格小于 $k$，则 Buber 当天只能使用更少的核心数（即租用所有可用的核心）；否则，Buber 当天恰好租用 $k$ 个核心。

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.

输入的第一行包含三个整数 $n$、$k$ 和 $m$（$1 \le n,k \le 10^6$，$1 \le m \le 2\cdot10^5$），分别表示需要分析的天数、期望的每日核心数以及资费方案的数量。

接下来的 $m$ 行每行描述一个资费方案。每行包含四个整数 $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$），其中 $l_i$ 和 $r_i$ 分别表示第 $i$ 个资费方案的起始日与终止日，$c_i$ 表示核心数量，$p_i$ 表示在第 $i$ 个资费方案下每日租用单个核心的价格。

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

输出一个整数——Buber 需要支付的最少金额。