Flip and Adjust

AtCoder

IDabc271_d

Time2000ms

Memory256MB

Difficulty—

There are $N$ cards with an integer written on each side. Card $i$ $(1 \leq i \leq N)$ has an integer $a_i$ written on the front and an integer $b_i$ written on the back. You may choose whether to place each card with its front or back side visible. Determine if you can place the cards so that the sum of the visible integers exactly equals $S$. If possible, find a placement of the cards to realize it. ## Constraints * $1 \leq N \leq 100$ * $1 \leq S \leq 10000$ * $1 \leq a_i, b_i \leq 100 \, (1 \leq i \leq N)$ * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $S$ $a_1$ $b_1$ $\vdots$ $a_N$ $b_N$ [samples]

Samples

Input #1

Output #1

Yes
THH

For example, the following placements make the sum of the visible integers exactly equal $S (= 11)$:

*   Place the $1$\-st card with its front side visible, $2$\-nd with its back, and $3$\-rd with its back.
*   Place the $1$\-st card with its back side visible, $2$\-nd with its front, and $3$\-rd with its front.

Therefore, outputs like `HTT` and `THH` are accepted.

Input #2

Output #2

No

You cannot place the cards so that the sum of the visible integers exactly equals $S (= 25)$.

API Response (JSON)

{
  "problem": {
    "name": "Flip and Adjust",
    "description": {
      "content": "There are $N$ cards with an integer written on each side. Card $i$ $(1 \\leq i \\leq N)$ has an integer $a_i$ written on the front and an integer $b_i$ written on the back. You may choose whether to pla",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc271_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ cards with an integer written on each side. Card $i$ $(1 \\leq i \\leq N)$ has an integer $a_i$ written on the front and an integer $b_i$ written on the back.\nYou may choose whether to pla...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments