Crazy Fences

No attempts yetTime limit1sMemory limit128 MB

Problem

A farmer redesigns the farm by setting up $N$ ($1 \le N \le 500$) new fences between the pastures. Each fence is a horizontal or vertical line segment in the 2D plane. If two fences meet, they meet only at their endpoints.

There are $C$ ($1 \le C \le 500$) cows on the farm. Each cow stands at a point that lies on no fence, and no two cows share the same point. Two cows belong to the same community if one can walk to the other without ever touching a fence. Determine the size of the largest community.

Input

  • Line 1: two space-separated integers $N$ and $C$.
  • Lines $2$ to $N+1$: each line contains four integers $x_1$, $y_1$, $x_2$, $y_2$, describing a fence running from point $(x_1, y_1)$ to point $(x_2, y_2)$. Every fence is vertical ($x_1 = x_2$) or horizontal ($y_1 = y_2$). All coordinates lie between $0$ and $1{,}000{,}000$.
  • Lines $N+2$ to $N+1+C$: each line contains two integers $x$ and $y$, the position of a cow. All coordinates lie between $0$ and $1{,}000{,}000$.

Output

  • Line 1: the number of cows in the largest community.

Hint

Two cows share a community exactly when a continuous path connects their positions without ever touching a fence. Because fences meet only at their endpoints, a fence with a free (dangling) end does not fully seal off a region, so a cow can simply walk around that open end. Only fences that together enclose an area separate one community from another.