← 返回题目列表

AtCoder · typical90_bd

056. 福袋(★5)

中文机器翻译题面 查看原题

配点: 5 点

問題文

在高桥屋百货公司, 首次销售将持续N 天。 在
i (1 \leq i \leq N) 日,A_i 日元福袋A和 B_i 日元福袋B将被出售。

高桥君是 N 我每天都会去高桥屋买福袋A或福袋B。(你不能不买任何东西。) 在
N 天内购买 N 福袋总数正好是 S 我想用日元购买。

由于高桥君不擅长算计,所以你应该代他制定购买符合条件的福袋的计划。
如果没有此类购买计划,请报告。

制約

  • 1 \leq N \leq 100
  • 1 \leq S \leq 10^5
  • 1 \leq A_i, B_i \leq 10^5 (1 \leq i \leq N)
  • 所有输入值均为整数

入力

输入是按以下格式从标准输入给出的。

N S
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

计划满足问题陈述中的条件的购买如下。 请将其输出为 N 字符串 T 。

  • i (1 \leq i \leq N) 如果您在 T_i= 'A',如果您想购买福袋B, T_i= 'B'

如果没有符合条件的采购计划。 'Impossible' 。


入力例 1

3 34
3 14
15 9
26 5

出力例 1

BAB

如果您按以下方式购买,则总金额将为 14+15+5=34 是日元。

  • 1 当天的福袋B(14 円)
  • 2 当天福袋A(15 円)
  • 3 当天的福袋B(5 円)

入力例 2

5 77
1 16
3 91
43 9
4 26
23 11

出力例 2

BABBA

如果您这样购买,总金额将为 16+3+9+26+23=77 是日元。
除此之外,BAAAB 但总金额是 16+3+43+4+11=77 答案是日元,所以答案是正确的。


入力例 3

5 59
8 13
55 5
58 8
23 14
4 61

出力例 3

Impossible

可能没有满足条件的购买方式。