CF1070C Cloud Computing

$\text{Buber}$ 是一家致力于浪费投资者的钱的 $\text{Berland}$ 技术公司。最近，$\text{Buber}$ 决定将他的设施转移到云端。公司决定连续 $n$ 天云端租用 $\text{CPU}$。$\text{Buber}$ 每天都要租用 $k$ 个 $\text{CPU}$。 云端供应商提供$\ m\ $个租用计划，第$i$个计划有如下的特征： - $l_i,r_i$ 表示第 $i$ 个计划从第 $l_i$ 天开始，第 $r_i$ 天结束。 - $c_i$ 表示第 $i$ 个计划中，每天最多租用 $\text{CPU}$ 个数。 - $p_i$ 表示第 $i$ 个计划中，租用一个 $\text{CPU}$ 一天的花费。 $\text{Buber}$ 可以同时使用多个计划，即他可以在第 $x$ 天在每个进行中的计划（即 $l_i\le x\le r_i$）中租用 $[0,c_i]$ 个 $\text{CPU}$. 现在 $\text{Buber}$ 告诉你正整数 $k$，表示每天所需的 $\text{CPU}$ 个数（如果某一天无论怎么租用都不能租到 $k$ 个，他也希望租尽量多的 $\text{CPU}$）。请你告诉他，他在这 $n$ 天中最少需要花费多少钱来租用 $\text{CPU}$？

第一行，三个正整数 $n,k,m$ （$1≤n,k≤10^6,1≤m≤2\times 10^5$），意义如上； 下面 $m$ 行，每行四个正整数表示$\ l_i,r_i,c_i,p_i$（$1≤l_i≤r_i≤n,1≤c_i≤p_i≤10^6$），即第 $i$ 个计划的特征。

仅一个正整数表示 $\text{Buber}$ 最少可以花费的钱。