D - Flip and Adjust Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

両面に整数が書かれたカードが N 枚あり、i \, (1 \leq i \leq N) 枚目のカードの表には a_i が、裏には b_i が書かれています。

あなたは、それぞれのカードについて、表を上に向けて置くか裏を上に向けて置くかを自由に決めることができます。

上に向けられた面に書かれた整数の総和がちょうど S となるようにカードを置くことができるか判定し、可能ならそのようなカードの置き方の一例を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq S \leq 10000
  • 1 \leq a_i, b_i \leq 100 \, (1 \leq i \leq N)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N S
a_1 b_1
\vdots
a_N b_N

出力

まず、上に向けられた面に書かれた整数の総和がちょうど S となるようにカードを置くことができるならば Yes を、できなければ No を出力し、改行せよ。

さらに、そのようにカードを置くことができるならば、カードの置き方を表す H および T のみからなる長さ N の文字列を出力せよ。
この文字列の i \, (1 \leq i \leq N) 文字目は、i 枚目のカードを表を上に向けて置くなら H、裏を上に向けて置くなら T でなければならない。
条件を満たすカードの置き方が複数考えられる場合、どれを出力しても正解となる。

入力例 1

3 11
1 4
2 3
5 7

出力例 1

Yes
THH

例えば次のように置くことで、上に向けられた面に書かれた整数の総和がちょうど S (= 11) となります。

  • 1 枚目は表、2 枚目は裏、3 枚目は裏を上に向けて置く。
  • 1 枚目は裏、2 枚目は表、3 枚目は表を上に向けて置く。

よって、HTT や THH といった出力が正解となります。

入力例 2

5 25
2 8
9 3
4 11
5 1
12 6

出力例 2

No

上に向けられた面に書かれた整数の総和がちょうど S (= 25) となるようにカードを置くことはできません。

Score : 400 points

Problem Statement

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

Output

First, print Yes if you can make the sum of the visible integers exactly equal S, and No otherwise, followed by a newline.

Additionally, if such a placement is possible, print a string of length N consisting of H and T that represents the placement of the cards to realize it.
The i-th (1 \leq i \leq N) character should be H if the i-th card should be placed with its front side visible, and T with its back.
If there are multiple possible placements to realize the sum, printing any of them is accepted.

Sample Input 1

3 11
1 4
2 3
5 7

Sample 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.

Sample Input 2

5 25
2 8
9 3
4 11
5 1
12 6

Sample Output 2

No

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