← 返回题目列表

Codeforces · 1070/C

C. 云计算

中文机器翻译题面 查看原题

Buber 是一家专门从事浪费投资者资金的 Berland 科技公司。最近,Buber 决定将其基础设施转移到云端。该公司决定在云中连续租用$$$n$$$天的CPU核心,编号从$$$1$$$到$$$n$$$。 Buber 每天需要 $$$k$$$ 个 CPU 核心。

云提供商提供 $$$m$$$ 资费计划,第 $$$i$$$ 资费计划具有以下参数:

- $$$l_i$$$ 和 $$$r_i$$$ — 第 $$$i$$$ 资费计划仅适用于从 $$$l_i$$$ 到 $$$r_i$$$(含)的日期,
- $$$c_i$$$ — 第 $$$i$$$ 资费计划中每天可供出租的核心数量,
- $$$p_i$$$ — 第 $$$i$$$ 资费计划中每天租用一个核心的价格。

Buber 可以在资费计划之间任意共享其计算核心需求。 Buber 每天可以在每个可用计划上租用任意数量的核心(从 0 到 $$$c_i$$$)。资费计划中租用的核心数量每天可能会任意变化。

求 Buber 在 $$$n$$$ 天(从 $$$1$$$ 到 $$$n$$$ 之间为其工作支付的最低金额)。如果某一天所有可用资费计划的核心总数严格小于 $$$k$$$,那么这一天 Buber 将必须在更少的核心上工作(并且它会租用所有可用的核心),否则 Buber 今天将恰好租用 $$$k$$$ 核心。

输入

输入的第一行包含三个整数 $$$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$$$ 个资费计划中单个核心的每日租金价格。

输出

打印一个整数——Buber 将支付的最低金额。

示例

输入 #1

5 7 3
1 4 5 3
1 3 5 2
2 5 10 1

输出 #1

44

输入 #2

7 13 5
2 3 10 7
3 5 10 10
1 2 10 6
4 5 10 9
3 4 10 8

输出 #2

462

输入 #3

4 100 3
3 3 2 5
1 1 3 2
2 4 4 4

输出 #3

64