Score : $400$ points

问题描述

设有 $N$ 张卡片，每张卡片上都写有一个整数。第 $i$ 张卡片 $(1 \leq i \leq N)$ 的正面写着整数 $a_i$，背面则写着整数 $b_i$。

你可以选择将每张卡片正面或反面朝上放置。

判断是否存在一种放置方式，使得所有可见整数之和恰好等于 $S$。如果可能，请找出实现这一目标的卡片放置方案。

以上为通义千问 qwen-max 翻译，仅供参考。

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)$.

update @ 2024/3/10 11:25:35