Description

Given a set $I$ of $n$ open line segments in the plane $x-O-y$, and a positive integer $k$. Design an algorithm to select a subset $S \subseteq I$ such that, for any point $p$ on the $x$-axis, the number of open line segments in $S$ that intersect the line $x = p$ does not exceed $k$, and $\sum\limits_{z\in S} |z|$ is maximized. Such a subset $S$ is called the longest $k$-overlap set of open line segments of $I$. The value $\sum\limits_{z\in S} |z|$ is called the length of the longest $k$-overlap segment set.

For any open line segment $z$ with endpoints $(x_0, y_0)$ and $(x_1, y_1)$, its length $|z|$ is defined as:

Given the open line segment set $I$ and the positive integer $k$, compute the length of the longest $k$-overlap open segment set of $I$.

Input Format

The first line contains $2$ positive integers $n$ and $k$, denoting the number of open line segments and the allowed overlap count.

The next $n$ lines each contain $4$ integers, giving the coordinates of the $2$ endpoints of an open line segment.

Output Format

Output the computed length of the longest $k$-overlap segment set.

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

17

Hint

Constraints: $1 \leq n \leq 500$, $1 \leq k \leq 13$, and all coordinates are within the int range.

Translated by ChatGPT 5