CF1106E Lunar New Year and Red Envelopes

新年就要到啦，Bob 打算去要很多红包！不过要红包是一件很费时间的事情。 我们假设从第 $1$ 秒开始共有 $n$ 秒，第 $i$ 个红包可以在第 $s_i$ 到 $t_i$ 秒（包括端点）收集，并且其中有 $w_i$ 元。如果 Bob 拿了第 $i$ 个红包，那么他直到第 $d_i$ 秒后（不包括$d_i$）才可以继续收集红包。其中 $s_i \leq t_i \leq d_i$。 Bob是一个贪心的人，他贪心地收集红包：如果他在第 $x$ 秒有红包可以收集，他就会选择其中钱最多的那个红包。如果这样的红包有多个，他就选 $d$ **最大**的那个红包。如果还是有多个选择，他就随便拿一个。 然而他的女儿 Alice 并不想他的爸爸拿到太多钱。她可以干扰 Bob 最多 $m$ 次。如果 Alice 在第 $x$ 秒干扰 Bob，在这一秒 Bob 就不能收集红包，然后下一秒 Bob 会继续用自己的策略收集。 现在请你求出如果 Alice 采用最优的策略，Bob 能拿到的最少钱数。

第一行三个整数 $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)$

输出一个整数代表 Alice 采用最优的策略后 Bob 能拿到的最少钱数。

在样例 1 中，Alice 不能干扰 Bob。因此，Bob 将在第 $1,5$ 秒领红包，总共收集 $13$ 块钱。 在样例 2 中，Alice 的最优策略是在第 $1$ 秒干扰 Bob。因此，Bob 只能领第二个红包，总共获得 $2$ 块钱。可以证明这是最优的。