AT_abc271_d [ABC271D] Flip and Adjust

题目描述

有 $N$ 张卡片，每张卡片的正反两面分别写有整数。第 $i$ 张卡片的正面写有 $a_i$，反面写有 $b_i$。

你可以自由决定每张卡片是正面朝上还是反面朝上。

请判断是否可以通过选择每张卡片的朝向，使得朝上的面上的整数之和恰好等于 $S$。如果可以，请给出一种可行的卡片放置方式。

输入格式

输入以如下格式从标准输入读入。

$N$ $S$
$a_1$ $b_1$
$\vdots$
$a_N$ $b_N$

输出格式

首先，如果存在一种卡片放置方式，使得朝上的面上的整数之和恰好等于 $S$，则输出 Yes，否则输出 No，并换行。

如果存在可行方案，则在下一行输出一个仅由 H 和 T 组成的长度为 $N$ 的字符串，表示卡片的放置方式。
第 $i$ 个字符为 H 表示第 $i$ 张卡片正面朝上，为 T 表示反面朝上。
如果存在多种方案，输出任意一种均可。

输入输出样例 #1

输入 #1

3 11
1 4
2 3
5 7

输出 #1

Yes
THH

输入输出样例 #2

输入 #2

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

输出 #2

No

说明/提示

限制条件

• $1 \leq N \leq 100$
• $1 \leq S \leq 10000$
• $1 \leq a_i, b_i \leq 100\ (1 \leq i \leq N)$
• 输入均为整数

样例解释 1

例如，可以如下放置卡片，使得朝上的面上的整数之和恰好为 $S (= 11)$。

• 第 1 张卡片正面朝上，第 2 张卡片反面朝上，第 3 张卡片反面朝上。
• 第 1 张卡片反面朝上，第 2 张卡片正面朝上，第 3 张卡片正面朝上。
  因此，HTT 或 THH 等输出均为正确答案。

样例解释 2

无法通过任何卡片放置方式，使得朝上的面上的整数之和恰好为 $S (= 25)$。

由 ChatGPT 4.1 翻译