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≤x≤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$ ⋅ $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}$最少可以花费的钱。