{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e♔♕♖♗♘♙♚♛♜♝♞♟\u003c/p\u003e\n\n\u003cp\u003eBuber是一家专门浪费投资者资金的Berland科技公司。最近,Buber决定将其基础设施转移到云端。该公司决定在$$$n$$$连续的日子里租用云端的CPU核心,这些日子从$$$1$$$到$$$n$$$编号。Buber每天需要$$$k$$$个CPU核心。\u003c/p\u003e\u003cp\u003e云服务提供商提供$$$m$$$种费率计划,第$$$i$$$种费率计划的特征如下:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$l_i$$$ 和 $$$r_i$$$ — 第$$$i$$$种费率计划仅在从$$$l_i$$$到$$$r_i$$$(包括)的日子可用, \u003c/li\u003e\u003cli\u003e $$$c_i$$$ — 第$$$i$$$种费率计划每天可租用的核心数, \u003c/li\u003e\u003cli\u003e $$$p_i$$$ — 第$$$i$$$种费率计划每天租用一个核心的价格。 \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eBuber可以在不同的费率计划之间任意分配其核心需求。每天,Buber可以在每个可用的计划上租用任意数量的核心(从0到$$$c_i$$$)。在每个费率计划上租用的核心数量可以每天任意变化。\u003c/p\u003e\u003cp\u003e找到Buber在从$$$1$$$到$$$n$$$的$$$n$$$天工作的最小花费。如果一天内所有可用费率计划的核心总数严格小于$$$k$$$,那么这一天Buber将不得不使用更少的核心(并且租用所有可用的核心),否则Buber将租用恰好$$$k$$$个核心。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入的第一行包含三个整数$$$n$$$、$$$k$$$和$$$m$$$($$$1 \\le n,k \\le 10^6, 1 \\le m \\le 2\\cdot10^5$$$) — 要分析的天数,每天所需的核心数,费率计划的数量。\u003c/p\u003e\u003cp\u003e接下来的$$$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$$$种费率计划每日租用单个核心的价格。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数 — Buber将支付的最小金额。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 7 3\n1 4 5 3\n1 3 5 2\n2 5 10 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e44\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 13 5\n2 3 10 7\n3 5 10 10\n1 2 10 6\n4 5 10 9\n3 4 10 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e462\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 100 3\n3 3 2 5\n1 1 3 2\n2 4 4 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e64\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}