Cover the Most Points with an Axis-Aligned Rectangle of Bounded Perimeter

Place an axis-aligned rectangle with perimeter at most P to cover as many supplied two-dimensional points as possible.

Function Signature

maximum_covered_points(points: list[list[int]], P: int) -> int

Geometry Rules

• Rectangle sides are parallel to the coordinate axes.
• Its width and height are nonnegative real numbers and must satisfy 2 * (width + height) <= P.
• For this exercise, zero width or zero height is allowed, so collinear or coincident points can be covered by a degenerate rectangle.
• Points on the boundary count as covered.
• Repeated coordinates count as separate input points.
• Rectangle coordinates need not be integers.

The at-most perimeter, boundary inclusion, and degenerate-rectangle rules are explicit conventions for this exercise.

Output

Return the maximum number of input points covered by one such rectangle. Return 0 for no points.

Constraints

• 0 <= len(points) <= 200.
• Each point is [x, y] with integer coordinates in [-1000000, 1000000].
• 0 <= P <= 1000000000.

Examples

Input: points = [[0,0],[2,0],[0,1],[2,1],[10,10]], P = 6

Output: 4

A width-2, height-1 rectangle covers the first four points.

Input: points = [[1,1],[1,1],[2,1]], P = 0

Output: 2

Input: points = [[0,0],[3,0]], P = 5

Output: 1