农历新年快到了,鲍勃要收到红包了,钱数不胜数!但收红包钱本身就是一个耗时的过程。
让我们用数学的方式来描述这个问题。考虑从时间 $$$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$$$。