AT_abc441_f [ABC441F] Must Buy

一家商店出售 $N$ 件商品，编号分别为商品 $1$、商品 $2$、$\ldots$、商品 $N$。 第 $i$ 件 $(1\leq i\leq N)$ 商品的价格为 $P_i$ 日元，价值为 $V_i$。该商店每种商品只有一件存货。 高桥想选择一些商品，使总价最多为 $M$ 日元。 在这里，可以保证 $M$ 至少是任何一件商品的价格。也就是说，对于任意 $1\leq i\leq N$，都存在一种方法来选择商品，使得总价最多为 $M$ 日元，并且包含商品 $i$。 对于每个 $1\leq i\leq N$，确定商品 $i$ 属于以下三类中的哪一类： - A 类：为了使所选商品的总价值最大（同时使总价不超过 $M$ 日元），必须选择该商品。 - B 类：为了使所选商品的总价值最大（同时使总价不超过 $M$ 日元），可以选择该商品，也可以不选择该商品。 - C 类：要使所选商品的总价值最大（同时使总价不超过 $M$ 日元），则绝对不能选择该商品。

输入内容按如下格式给出： >$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$ 解释 在选择商品时，如果总价最多为 $7$ 日元，则可能的最大总价值为 $30$ 日元，可以通过以下方法之一实现： - 选择商品 $1$、$2$ 和 $5$。 - 选择商品 $4$ 和 $5$。 (没有其他方法可以选择商品，使总价最多为 $7$ 日元，总价值为 $30$ 日元）。 因此，每个商品的类别如下： - 商品 $5$ 是为了使所选商品的总价值最大而必须选择的商品（A 类）。 - 商品 $1$、$2$ 和 $4$ 是为了使所选商品的总价值最大而可能选择或不选择的商品（B 类）。 - 商品 $3$ 是一个绝对不可能被选中来最大化所选商品总价值的商品（C 类）。 因此，根据输出格式，打印 `BBCBA`。 ### 样例 $2$ 解释 从商品 $3$、$4$、$5$ 中任选一项，并选择商品 $6$ 和 $7$，使得总价值最大。 请注意，即使两个商品的价格和价值均相同，它们仍会被区分为不同的商品。 ### 数据规模与约定 对于 $100\%$ 的数据: - $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$ - 所有输入值均为整数。