Maximizing Ray Coverage

You are given n line segments in the plane. Each line segment is defined by the coordinates of its two endpoints. From the origin, you may shoot at most k rays. A ray with angle \(\theta\) (in radians) will "pierce" a line segment if and only if it intersects that segment. However, each segment can be pierced at most once even if several rays pass through it.

For each segment, consider the two rays drawn from the origin to its endpoints. Let \(\theta_1\) and \(\theta_2\) (in \( [0,2\pi) \)) denote the angles of these two rays. It is guaranteed that the difference between \(\theta_1\) and \(\theta_2\) does not exceed \(\pi\) (so the set of all rays that intersect the segment is exactly the closed interval </em>[ min(\(\theta_1,\theta_2\)), max(\(\theta_1,\theta_2\)) ]</em> in radians).

Your task is to choose at most k rays (i.e. choose at most k angles between \(0\) and \(2\pi\)) such that the total number of segments pierced (each counted at most once) is maximized.

Input constraints and hints: You may assume that \(n\) is small enough (for example, \(n \le 100\)) so that an \(O(n^2 k)\) dynamic programming solution will run in time.

Note: It is always optimal to choose the rays at some endpoint of one of the intervals.

inputFormat

The first line contains two integers \(n\) and \(k\) (the number of segments and the maximum number of rays you can shoot).

Each of the next \(n\) lines contains four integers \(x_1\), \(y_1\), \(x_2\), \(y_2\) representing the coordinates of the two endpoints of a segment.

It is guaranteed that for each segment, if we compute the angles (in radians) of the rays from the origin to its endpoints (adjusted to lie in \([0, 2\pi)\)), the difference between these two angles does not exceed \(\pi\).

outputFormat

Output a single integer: the maximum number of line segments that can be pierced by shooting at most \(k\) rays from the origin.

sample

3 1
1 0 0 1
2 0 0 2
1 1 -1 1

3