#6227. 「网络流 24 题」最长 k 可重线段集问题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

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

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

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

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

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

输入格式

文件的第一 行有二 个正整数 \text{n} \text{k} ,分别表示开线段的 个数和开线段的可重迭数。接下来的 \text{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\leq500, 1 \leq k \leq 13 .