最长k可重线段集问题

题目描述

给定平面 $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|$ 定义为: $$|z|=\lfloor\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}\rfloor$$ 对于给定的开线段集合 $I$ 和正整数 $k$,计算开线段集合 $I$ 的最长 $k$ 可重线段集的长度。

输入输出格式

输入格式


文件的第一 行有 $2$ 个正整数 $n$ 和 $k$,分别表示开线段的个数和开线段的可重叠数。 接下来的 $n$ 行,每行有 $4$ 个整数,表示开线段的 $2$ 个端点坐标。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

17

说明

$1\leq n\leq500$ $1 \leq k \leq 13$