Jigsaw

AtCoder

IDagc017_e

Time2000ms

Memory256MB

Difficulty—

We have $N$ irregular jigsaw pieces. Each piece is composed of three rectangular parts of width $1$ and various heights joined together. More specifically: * The $i$\-th piece is a part of height $H$, with another part of height $A_i$ joined to the left, and yet another part of height $B_i$ joined to the right, as shown below. Here, the bottom sides of the left and right parts are respectively at $C_i$ and $D_i$ units length above the bottom side of the center part. ![image](https://atcoder.jp/img/agc017/2b6cd7f4500d3621bc18de407f167522.png) Snuke is arranging these pieces on a square table of side $10^{100}$. Here, the following conditions must be held: * All pieces must be put on the table. * The entire bottom side of the center part of each piece must touch the front side of the table. * The entire bottom side of the non-center parts of each piece must either touch the front side of the table, or touch the top side of a part of some other piece. * The pieces must not be rotated or flipped. Determine whether such an arrangement is possible. ## Constraints * $1 \leq N \leq 100000$ * $1 \leq H \leq 200$ * $1 \leq A_i \leq H$ * $1 \leq B_i \leq H$ * $0 \leq C_i \leq H - A_i$ * $0 \leq D_i \leq H - B_i$ * All input values are integers. ## Input Input is given from Standard Input in the following format: $N$ $H$ $A_1$ $B_1$ $C_1$ $D_1$ $A_2$ $B_2$ $C_2$ $D_2$ : $A_N$ $B_N$ $C_N$ $D_N$ [samples]

Samples

Input #1

Output #1

YES

The figure below shows a possible arrangement.
![image](https://atcoder.jp/img/agc017/27db184b6924d4cec5077a54b505706a.png)

Input #2

Output #2

NO

Input #3

Output #3

YES

API Response (JSON)

{
  "problem": {
    "name": "Jigsaw",
    "description": {
      "content": "We have $N$ irregular jigsaw pieces. Each piece is composed of three rectangular parts of width $1$ and various heights joined together. More specifically: *   The $i$\\-th piece is a part of height $",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc017_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have $N$ irregular jigsaw pieces. Each piece is composed of three rectangular parts of width $1$ and various heights joined together. More specifically:\n\n*   The $i$\\-th piece is a part of height $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments