You are given a set of N distinct points on a two-dimensional coordinate plane along with an even integer perimeter.

Your task is to position a rectangle so that it contains the largest possible number of given points.

A point is considered covered when it is either:

• strictly inside the rectangle, or
• located directly on one of its four sides.

The rectangle must be axis-aligned, meaning its sides cannot be rotated and must remain parallel to the coordinate axes.

The total length of all four sides must be exactly perimeter.

---

Rectangle Dimensions

Let the rectangle have:

• width = W
• height = H

Its perimeter is:

2 × W + 2 × H = perimeter

or equivalently:

W + H = perimeter / 2

For example, when:

perimeter = 10

the available (width, height) combinations are:

(1, 4)
(2, 3)
(3, 2)
(4, 1)

The rectangle can be translated to any position on the plane.

---

Required Function

The following structure is provided:

struct Point2D {
    int x;
    int y;
};

Implement the function:

int solution(vector<Point2D> &points, int perimeter);

The function must return the highest number of input points that can simultaneously lie inside or on the boundary of a valid rectangle.

---

Examples

Example 1

Input

points = [
    (1, 1),
    (-1, -1),
    (-2, 2),
    (2, 0)
]

perimeter = 10

Output

3

Explanation

A rectangle with dimensions 3 × 2 has perimeter:

2 × (3 + 2) = 10

It can be positioned to contain the following three points:

(-1, -1)
(1, 1)
(2, 0)

Hence, the maximum number of covered points is 3.

Illustration

          y
          ↑

   2      ● (-2,2)

   1          ┌──────────────● (1,1)
              │
   0          │                   ● (2,0)
              │
  -1          ● (-1,-1)
              └──────────────

          └────────────────────────→ x

---

Example 2

Input

points = [
    (0, 0),
    (-1, 3),
    (2, -2),
    (-2, -1),
    (-2, 0),
    (2, 3),
    (1, -1),
    (0, 1),
    (2, 0)
]

perimeter = 14

Output

7

Explanation

A valid rectangle with dimensions:

4 × 3

has perimeter:

2 × (4 + 3) = 14

By choosing an appropriate position for this rectangle, 7 of the 9 points can be covered.

Thus, the maximum possible number of covered points is 7.

Illustration

             y
             ↑

   3     ● (-1,3)                  ● (2,3)

   2

   1                    ● (0,1)

   0     ● (-2,0)       ● (0,0)       ● (2,0)

  -1     ● (-2,-1)                  ● (1,-1)

  -2                                  ● (2,-2)

             └──────────────────────────→ x

---

Constraints

• N is between 1 and 40.
• Every x coordinate is between -10 and 10.
• Every y coordinate is between -10 and 10.
• All points are different.
• perimeter is an even integer between 4 and 40.

The primary requirement is correctness; the input limits are small enough that an exhaustive search over possible rectangle dimensions and placements is acceptable.

---