← 返回题目列表

Codeforces · 1106/E

E. 农历新年和红包

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

农历新年快到了,鲍勃要收到红包了,钱数不胜数!但收红包钱本身就是一个耗时的过程。

让我们用数学的方式来描述这个问题。考虑从时间 $$$1$$$ 到 $$$n$$$ 的时间线。第$$$i$$$红包的领取时间为$$$s_i$$$至$$$t_i$$$(含),内含$$$w_i$$$金币。如果Bob选择领取第$$$i$$$个红包中的币,他只能在$$$s_i$$$和$$$t_i$$$(含)之间的整数时间点领取红包,并且在之后的$$$d_i$$$(含)时间之前他不能再领取红包。这里 $$$s_i \leq t_i \leq d_i$$$ 成立。

Bob是一个贪婪的人,他贪婪地收集金币——每当他能在某个整数时间$$$x$$$收集到金币时,他就收集到可用金币数量最多的红包。如果有多个信封的最大硬币数量相同,Bob 会选择参数 $$$d$$$ 最大的那个。如果还有多个选择,Bob 会随机选择一个。

然而,爱丽丝——他的女儿——不希望她的父亲得到太多的硬币。她可以在不超过 $$$m$$$ 整数时刻打扰鲍勃。如果Alice决定在$$$x$$$时刻打扰Bob,那么他在$$$x$$$时刻就无法做任何事情,并在$$$x + 1$$$(含)时刻恢复其通常的策略,这可能会导致丢失一些红包。

计算如果爱丽丝以最佳方式打扰鲍勃,鲍勃将获得的最小硬币数量。

输入

第一行包含三个非负整数$$$n$$$、$$$m$$$和$$$k$$$($$$1 \leq n \leq 10^5$$$、$$$0 \leq m \leq 200$$$、$$$1 \leq k \leq 10^5$$$),表示时间线的长度、 Alice可以打扰Bob的次数和红包总数分别是。

以下 $$$k$$$ 行描述了这些 $$$k$$$ 红包。第 $$$i$$$ 行包含四个正整数 $$$s_i$$$、$$$t_i$$$、$$$d_i$$$ 和 $$$w_i$$$ ($$$1 \leq s_i \leq t_i \leq d_i \leq n$$$, $$$1 \leq w_i \leq 10^9$$$) — 的时间段分别是第 $$$i$$$ 个信封可用、鲍勃在收集第 $$$i$$$ 个信封后可以继续收集的时间以及该信封中的硬币数量。

输出

输出一个整数——如果爱丽丝以最佳方式打扰鲍勃,鲍勃将获得的最少硬币数量。

示例

输入 #1

5 0 2
1 3 4 5
2 5 5 8

输出 #1

13

输入 #2

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

输出 #2

2

输入 #3

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

输出 #3

11

注意

在第一个样本中,Alice 没有机会打扰 Bob。因此Bob会在$$$1$$$和$$$5$$$时间领取红包内的币,总共领取$$$13$$$币。

在第二个示例中,Alice 应该在时间 $$$1$$$ 打扰 Bob。因此鲍勃跳过第一个信封,收集第二个信封,之后就不能做任何事情了。所以答案是$$$2$$$。