CF1106E.Lunar New Year and Red Envelopes

Lunar New Year is approaching, and Bob is going to receive some red envelopes with countless money! But collecting money from red envelopes is a time-consuming process itself.

Let's describe this problem in a mathematical way. Consider a timeline from time $1$ to $n$. The $i$-th red envelope will be available from time $s_i$ to $t_i$, inclusive, and contain $w_i$ coins. If Bob chooses to collect the coins in the $i$-th red envelope, he can do it only in an integer point of time between $s_i$ and $t_i$, inclusive, and he can't collect any more envelopes until time $d_i$ (inclusive) after that. Here $s_i \leq t_i \leq d_i$ holds.

Bob is a greedy man, he collects coins greedily — whenever he can collect coins at some integer time $x$, he collects the available red envelope with the maximum number of coins. If there are multiple envelopes with the same maximum number of coins, Bob would choose the one whose parameter $d$ is the largest. If there are still multiple choices, Bob will choose one from them randomly.

However, Alice — his daughter — doesn't want her father to get too many coins. She could disturb Bob at no more than $m$ integer time moments. If Alice decides to disturb Bob at time $x$, he could not do anything at time $x$ and resumes his usual strategy at the time $x + 1$ (inclusive), which may lead to missing some red envelopes.

Calculate the minimum number of coins Bob would get if Alice disturbs him optimally.

农历新年即将来临，Bob 将会收到一些装有大量金钱的红包！但收集红包中的金钱本身是一个耗时的过程。

我们用数学方式来描述这个问题：考虑一个从时刻 $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 将从中随机任选一个。

然而，Alice——他的女儿——不希望父亲获得过多硬币。她最多可在 $m$ 个整数时刻干扰 Bob。若 Alice 决定在时刻 $x$ 干扰 Bob，则 Bob 在时刻 $x$ 无法执行任何操作，并于时刻 $x + 1$（含）起恢复其常规策略，这可能导致他错过某些红包。

请计算：当 Alice 以最优策略进行干扰时，Bob 最终所能获得的硬币数的最小值。

The first line contains three non-negative integers $n$, $m$ and $k$ ($1 \leq n \leq 10^5$, $0 \leq m \leq 200$, $1 \leq k \leq 10^5$), denoting the length of the timeline, the number of times Alice can disturb Bob and the total number of red envelopes, respectively.

The following $k$ lines describe those $k$ red envelopes. The $i$-th line contains four positive integers $s_i$, $t_i$, $d_i$ and $w_i$ ($1 \leq s_i \leq t_i \leq d_i \leq n$, $1 \leq w_i \leq 10^9$) — the time segment when the $i$-th envelope is available, the time moment Bob can continue collecting after collecting the $i$-th envelope, and the number of coins in this envelope, respectively.

第一行包含三个非负整数 $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$ 个红包的有效时间段、Bob 在领取第 $i$ 个红包后可以继续领取红包的时间点，以及该红包中的金币数量。

Output one integer — the minimum number of coins Bob would get if Alice disturbs him optimally.

输出一个整数——如果爱丽丝以最优方式干扰鲍勃，鲍勃能得到的最少硬币数量。

In the first sample, Alice has no chance to disturb Bob. Therefore Bob will collect the coins in the red envelopes at time $1$ and $5$, collecting $13$ coins in total.

In the second sample, Alice should disturb Bob at time $1$. Therefore Bob skips the first envelope, collects the second one and can not do anything after that. So the answer is $2$.

在第一个样例中，Alice 无法干扰 Bob。因此 Bob 将在时刻 $1$ 和 $5$ 收集红色信封中的硬币，总共收集 $13$ 枚硬币。

在第二个样例中，Alice 应在时刻 $1$ 干扰 Bob。因此 Bob 跳过第一个信封，收集第二个信封，之后便无法再进行任何操作。故答案为 $2$。