U538070 抢红包

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

第一行三个整数$n$，$m$，$k$。 接下来$k$行，每行四个整数$s_i,t_i,d_i,w_i$。

输出一个整数，为晓莱采用最优的策略后晓梦能拿到的最少钱数。

$1\le s_i\le t_i\le d_i\le n,1\le w_i\le10^9$ 对于$30\%$的数据范围，$1\le n,k\le 10^3,0\le m\le20$。 对于$100\%$的数据范围，$1\le n,k\le 10^5,0\le m\le200$。