题目描述

给定平面 $x-O-y$ 上 $n$ 个开线段组成的集合 $I$，和一个正整数 $k$ 。试设计一个算法，从开线段集合 $I$ 中选取出开线段集合 $S\subseteq I$ ,使得在 $x$ 轴上的任何一点 $p$，$S$ 中与直线 $x=p$ 相交的开线段个数不超过 $k$，且$\sum\limits_{z\in S}|z|$达到最大。这样的集合 $S$ 称为开线段集合 $I$ 的最长 $k$ 可重线段集。$\sum\limits_{z\in S}|z|$ 称为最长 $k$ 可重线段集的长度。

对于任何开线段 $z$，设其断点坐标为 $(x_0,y_0)$ 和 $(x_1,y_1)$，则开线段 $z$ 的长度 $|z|$ 定义为：

对于给定的开线段集合 $I$ 和正整数 $k$，计算开线段集合 $I$ 的最长 $k$ 可重线段集的长度。

输入格式

文件的第一 行有 $2$ 个正整数 $n$ 和 $k$，分别表示开线段的个数和开线段的可重叠数。

接下来的 $n$ 行，每行有 $4$ 个整数，表示开线段的 $2$ 个端点坐标。

输出格式

程序运行结束时，输出计算出的最长 $k$ 可重线段集的长度。

4 2
1 2 7 3
6 5 8 3
7 8 10 5
9 6 13 9 

17

提示

$1\leq n\leq 500$，$1 \leq k \leq 13$，坐标值在 int 范围内。