题目描述

给定平面 $\red{\text{xoy}}$上 $\red{n}$ 个开线段组成的集合 $\red{\text{I}}$，和一个正整数 $\red{k}$,试设计一个算法。

从开线段集合 $\red{\text{I}}$ 中选取出开线段集合 $\red{\text{S}\in \text{I}}$,

使得在x轴上的任何一点 $\red{\text{p}}$ ， $\red{\text{S}}$ 中与直线 $\red{\text{x}=\text{p}}$ 相交的开线段个数不超过 $\red{\text{k}}$ ，

且 $\red{\sum_{\text{z} \in \text{S}}|z|}$ 达到最大。

这样的集合 $\red{\text{S}}$ 称为开线段集合 $\red{\text{I}}$ 的最长 $\red{\text{k}}$ 可重线段集的长度。

对于任何开线段 $\red{\text{z}}$，设其端点坐标为$\red{( x_0 , y_0 )}$ 和$\red{ ( x_1 , y_1 )}$，

则开线段 $\red{\text{z}}$ 的长度 $\red{|\text{z}|}$ 定义为： $\red{|z| = \lfloor \sqrt{ ( x_1 - x_0 ) ^ 2 + ( y_1 - y_0 )^2 } \rfloor}$

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

输入格式

文件的第一 行有二 个正整数 $\red{\text{n}}$ 和 $\red{\text{k}}$ ，分别表示开线段的 个数和开线段的可重迭数。接下来的 $\red{\text{n}}$ 行，每行有 $\red{4}$ 个整数，表示开线段的 $\red{2}$ 个端点坐标。

输出格式

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

样例

输入样例

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

输出样例

17

提示

$\red{1\leq n\, 1 \leq k \leq 13}$.