Grid and Tokens

AtCoder

IDabc205_f

Time2000ms

Memory256MB

Difficulty—

There is a grid with $H$ rows and $W$ columns. Let $(r, c)$ denote the square at the $r$\-th row from the top and $c$\-th column from the left. We have $N$ pieces. For the $i$\-th piece, we can choose to do one of the following: * Put it at a square $(r, c)$ such that $A_i \leq r \leq C_i$ and $B_i \leq c \leq D_i$. * Do not put it on the grid. However, we cannot put two pieces in the same row or the same column. At most how many pieces can we put on the grid? ## Constraints * $1 \leq H, W, N \leq 100$ * $1 \leq A_i \leq C_i \leq H$ * $1 \leq B_i \leq D_i \leq W$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $H$ $W$ $N$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ $\vdots$ $A_N$ $B_N$ $C_N$ $D_N$ [samples]

Samples

Input #1

Output #1

2

By putting the first piece at $(1, 1)$, the second piece at $(2, 2)$, and not putting the third piece on the grid, we can put two pieces on the grid. We cannot put three, so we should print $2$.

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Grid and Tokens",
    "description": {
      "content": "There is a grid with $H$ rows and $W$ columns. Let $(r, c)$ denote the square at the $r$\\-th row from the top and $c$\\-th column from the left. We have $N$ pieces. For the $i$\\-th piece, we can choose",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc205_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a grid with $H$ rows and $W$ columns. Let $(r, c)$ denote the square at the $r$\\-th row from the top and $c$\\-th column from the left.\nWe have $N$ pieces. For the $i$\\-th piece, we can choose...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments