Longest k-Overlapping Segments Set

Given a set \( I \) of \( n \) open line segments on the \( xOy \) plane and a positive integer \( k \), select a subset \( S\subseteq I \) such that for every vertical line \( x=p \) (with \( p \) being any real number), the number of open segments from \( S \) that intersect the line \( x=p \) does not exceed \( k \). The objective is to maximize the sum of the lengths of the segments in \( S \), where the length of an open segment \( z \) with endpoints \( (x_0,y_0) \) and \( (x_1,y_1) \) is defined by

$$|z|=\left\lfloor\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}\right\rfloor. $$

The maximum total length,

$$\sum_{z\in S}|z|,$$

is called the length of the longest \( k \)-overlapping segments set of \( I \). You are to compute this maximum total length.

Note: An open segment \( z \) defined by endpoints \( (x_0,y_0) \) and \( (x_1,y_1) \) is considered to cover exactly those points \( (x,y) \) for which \( x \) is strictly between \( \min(x_0,x_1) \) and \( \max(x_0,x_1) \) (endpoints are not included).

inputFormat

The first line contains two integers \( n \) and \( k \) (the number of segments and the maximum allowed overlaps, respectively).

Then, \( n \) lines follow. Each line contains four numbers \( x_0\, y_0\, x_1\, y_1 \) representing the coordinates of the two endpoints of an open segment.

You may assume that \( x_0, y_0, x_1, y_1 \) are integers.

outputFormat

Output a single integer representing the maximum total length of the longest \( k \)-overlapping segments set.

sample

3 1
0 0 2 0
1 0 3 0
2 0 4 0

4