A Piece of Cake

AtCoder

IDabc304_d

Time3000ms

Memory256MB

Difficulty—

There is a rectangular cake with some strawberries on the $xy$\-plane. The cake occupies the rectangular area $\lbrace (x, y) : 0 \leq x \leq W, 0 \leq y \leq H \rbrace$. There are $N$ strawberries on the cake, and the coordinates of the $i$\-th strawberry are $(p_i, q_i)$ for $i = 1, 2, \ldots, N$. No two strawberries have the same coordinates. Takahashi will cut the cake into several pieces with a knife, as follows. * First, cut the cake along $A$ different lines parallel to the $y$\-axis: lines $x = a_1$, $x = a_2$, $\ldots$, $x = a_A$. * Next, cut the cake along $B$ different lines parallel to the $x$\-axis: lines $y = b_1$, $y = b_2$, $\ldots$, $y = b_B$. As a result, the cake will be divided into $(A+1)(B+1)$ rectangular pieces. Takahashi will choose just one of these pieces to eat. Print the minimum and maximum possible numbers of strawberries on the chosen piece. Here, it is guaranteed that there are no strawberries along the edges of the final pieces. For a more formal description, refer to the constraints below. ## Constraints * $3 \leq W, H \leq 10^9$ * $1 \leq N \leq 2 \times 10^5$ * $0 \lt p_i \lt W$ * $0 \lt q_i \lt H$ * $i \neq j \implies (p_i, q_i) \neq (p_j, q_j)$ * $1 \leq A, B \leq 2 \times 10^5$ * $0 \lt a_1 \lt a_2 \lt \cdots \lt a_A \lt W$ * $0 \lt b_1 \lt b_2 \lt \cdots \lt b_B \lt H$ * $p_i \not \in \lbrace a_1, a_2, \ldots, a_A \rbrace$ * $q_i \not \in \lbrace b_1, b_2, \ldots, b_B \rbrace$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $W$ $H$ $N$ $p_1$ $q_1$ $p_2$ $q_2$ $\vdots$ $p_N$ $q_N$ $A$ $a_1$ $a_2$ $\ldots$ $a_A$ $B$ $b_1$ $b_2$ $\ldots$ $b_B$ [samples]

Samples

Input #1

Output #1

0 2

There are nine pieces in total: six with zero strawberries, one with one strawberry, and two with two strawberries. Therefore, when choosing just one of these pieces to eat, the minimum possible number of strawberries on the chosen piece is $0$, and the maximum possible number is $2$.

Input #2

Output #2

1 1

Each piece has one strawberry on it.

API Response (JSON)

{
  "problem": {
    "name": "A Piece of Cake",
    "description": {
      "content": "There is a rectangular cake with some strawberries on the $xy$\\-plane. The cake occupies the rectangular area $\\lbrace (x, y) : 0 \\leq x \\leq W, 0 \\leq y \\leq H \\rbrace$. There are $N$ strawberries on",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc304_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a rectangular cake with some strawberries on the $xy$\\-plane. The cake occupies the rectangular area $\\lbrace (x, y) : 0 \\leq x \\leq W, 0 \\leq y \\leq H \\rbrace$.\nThere are $N$ strawberries on...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments