F - Must Buy 解説 /

実行時間制限: 2.5 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

ある店に N 個の商品が売られており、商品 1, 商品 2, \ldots, 商品 N と番号づけられています。
商品 i (1\leq i\leq N) の値段は P_i 円で、価値は V_i です。どの商品も 1 つずつしか存在しません。

高橋君は、値段の合計が M 円以下となる範囲でいくつかの商品を選びます。
ここで、M は任意の商品の値段以上であることが保証されます。 すなわち、任意の 1\leq i\leq N について、値段の合計が M 円以下となる選び方であって商品 i を含むようなものが必ず存在します。

このとき、1\leq i\leq N それぞれについて、商品 i が以下の 3 つの分類のどれに該当するか判定してください。

  • 分類 A: （値段の合計が M 円以下となる範囲で）選んだ商品の価値の合計を最大にするには、その商品を必ず選ばなければならない。
  • 分類 B: （値段の合計が M 円以下となる範囲で）選んだ商品の価値の合計を最大にするには、その商品を選んでも選ばなくてもよい。
  • 分類 C: （値段の合計が M 円以下となる範囲で）選んだ商品の価値の合計を最大にするには、その商品を決して選んではならない。

制約

  • 1\leq N\leq 1000
  • 1\leq M\leq 5\times 10^4
  • 1\leq P_i\leq M
  • 1\leq V_i\leq 10^9
  • 入力はすべて整数

入力

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

N M
P_1 V_1
P_2 V_2
\vdots
P_N V_N

出力

A,B,C からなる長さ N の文字列を出力せよ。
商品 i (1\leq i\leq N) が分類 X（X は A,B,C のいずれか）に該当するとき、出力する文字列の i 文字目が X となるようにせよ。

入力例 1

5 7
2 5
2 5
3 5
3 10
3 20

出力例 1

BBCBA

値段の合計が 7 円以下となる範囲で商品を選んだ時の価値の合計としてあり得る最大値は 30 であり、これは

  • 商品 1 と商品 2 と商品 5 を選ぶ。
  • 商品 4 と商品 5 を選ぶ。

のいずれかによって達成できます。（これ以外に値段の合計が 7 円以下かつ価値の合計が 30 となる選び方はありません。）
これより、各商品の分類は次のようになります。

  • 商品 5 は、選んだ商品の価値の合計を最大にするには、必ず選ばなければならない商品（分類 A ）です。
  • 商品 1, 商品 2, 商品 4 は、選んだ商品の価値の合計を最大にするために、選んでも選ばなくてもよい商品（分類 B ）です。
  • 商品 3 は、選んだ商品の価値の合計を最大にするには、決して選んではならない商品（分類 C ）です。

よって、出力形式に従って、BBCBA を出力します。

入力例 2

7 3
1 1
1 1
1 2
1 2
1 2
1 3
1 3

出力例 2

CCBBBAA

商品 3, 商品 4, 商品 5 のうちいずれか 1 つと、商品 6, 商品 7 を選んだ時に価値の合計が最大となります。
値段と価値がともに等しい商品であっても、商品としては区別されることに注意してください。

Score : 500 points

Problem Statement

A store sells N items, numbered as item 1, item 2, \ldots, item N.
Item i (1\leq i\leq N) has a price of P_i yen and a value of V_i. The store has only one stock of each item.

Takahashi chooses some items such that the total price is at most M yen.
Here, it is guaranteed that M is at least the price of any item. That is, for any 1\leq i\leq N, there exists a way to choose items such that the total price is at most M yen and item i is included.

For each 1\leq i\leq N, determine which of the following three categories item i falls into:

  • Category A: To maximize the total value of the chosen items (while keeping the total price at most M yen), that item must be chosen.
  • Category B: To maximize the total value of the chosen items (while keeping the total price at most M yen), that item may or may not be chosen.
  • Category C: To maximize the total value of the chosen items (while keeping the total price at most M yen), that item must never be chosen.

Constraints

  • 1\leq N\leq 1000
  • 1\leq M\leq 5\times 10^4
  • 1\leq P_i\leq M
  • 1\leq V_i\leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
P_1 V_1
P_2 V_2
\vdots
P_N V_N

Output

Print a string of length N consisting of A, B, and C.
If item i (1\leq i\leq N) falls into category X (where X is A, B, or C), the i-th character of the output string should be X.

Sample Input 1

5 7
2 5
2 5
3 5
3 10
3 20

Sample Output 1

BBCBA

The maximum possible total value when choosing items such that the total price is at most 7 yen is 30, which can be achieved by one of the following:

  • Choosing items 1, 2, and 5.
  • Choosing items 4 and 5.

(There is no other way to choose items such that the total price is at most 7 yen and the total value is 30.)
Thus, the category of each item is as follows:

  • Item 5 is an item that must be chosen to maximize the total value of the chosen items (category A).
  • Items 1, 2, and 4 are items that may or may not be chosen to maximize the total value of the chosen items (category B).
  • Item 3 is an item that must never be chosen to maximize the total value of the chosen items (category C).

Therefore, according to the output format, print BBCBA.

Sample Input 2

7 3
1 1
1 1
1 2
1 2
1 2
1 3
1 3

Sample Output 2

CCBBBAA

The total value is maximized when choosing any one of items 3, 4, 5, along with items 6 and 7.
Note that even if items have equal prices and values, they are still distinguished as different items.