题目描述

有 $n$ 条互不相交，平行于 $y$ 轴的线段，会给线段覆盖的格点打下标记，当这条线段打下的标记被完全清除的时候，你会得到 $p_i$ 的分数。

你有 $m$ 次操作机会，每次可以任选若干段平行于 $y$ 轴，纵坐标互不相交的线段，并清除这些位置上的标记。

求最大得分。

输入格式

第一行两个整数 $n,m$。
接下来 $n$ 行，每行四个整数 $x,y_1,y_2,p$，表示第 $i$ 条线段横坐标为 $x$，纵坐标在 $y_1$ 到 $y_2$ 之间，权值为 $p$。

输出格式

输出一个整数，表示计算出的最大得分。

5 2
1 1 3 2
1 4 6 2
2 3 5 2
3 2 4 2
4 3 4 1

8

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 10^3$，$1\leq m\leq100$，$1\leq y_1,y_2\leq 5\times 10^3$，$1\leq p\leq 10^5$，$1\leq x\leq 5\times 10^3$。

数据不保证 $y_1\leq y_2$，请注意特判。