P12712 [KOI 2021 Round 1] 超矩形

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

我们可以考虑 1 维空间中的线段、2 维空间中的矩形、3 维空间中的长方体： - 线段的大小可以用变量 $A$ 表示，其长度为 $A$； - 矩形的大小可以用两个变量 $A$ 和 $B$ 表示，其面积为 $A \cdot B$； - 长方体的大小可以用三个变量 $A$、$B$、$C$ 表示，其体积为 $A \cdot B \cdot C$。  在四维空间中，可以定义一个由四个变量 $A$、$B$、$C$、$D$ 表示大小的“超矩形”。其“体积”为 $A \cdot B \cdot C \cdot D$。 起初，变量 $A$、$B$、$C$、$D$ 的值分别为 $A_0$、$B_0$、$C_0$、$D_0$。 你有 $N$ 张“卡牌”，每张卡牌上写有一个字母 $T_i$（在 $A$、$B$、$C$、$D$ 中取一个）和一个正整数 $U_i$，表示该卡牌会使对应变量的值增加 $U_i$。每张卡牌最多只能使用一次，用完即消失。 你希望通过**恰好选用 $K$ 张卡牌**（选出的卡牌可以按任意顺序使用），来最大化超矩形的体积。请编写程序，输出一组选牌及使用顺序，使体积最大化。 若存在多种方式达到最大体积，任选其中一种方案输出即可。

第一行输入两个整数 $N$ 和 $K$，中间以空格隔开。 第二行输入初始变量值 $A_0$、$B_0$、$C_0$、$D_0$，中间以空格隔开。 接下来的 $N$ 行中，第 $i$ 行输入第 $i$ 张卡牌的内容，即 $T_i$ 和 $U_i$，中间以空格隔开。

输出 $K$ 行，依次表示选中的卡牌及其使用顺序，按与输入格式相同的方式给出。

**约束条件** - 所有给定数值均为整数 - $1 \leq K \leq N \leq 200\,000$ - $1 \leq A_0, B_0, C_0, D_0 \leq 1\,000\,000$ - 对所有 $1 \leq i \leq N$，$T_i \in \{A, B, C, D\}$ - 对所有 $1 \leq i \leq N$，$1 \leq U_i \leq 1\,000\,000$ **子任务** 1. （8 分）$N \leq 10$，$A_0, B_0, C_0, D_0 \leq 10$，且所有 $U_i \leq 10$ 2. （6 分）$B_0 = C_0 = D_0 = 1$，所有 $T_i = A$ 3. （15 分）$N \leq 300$，$A_0, B_0, C_0, D_0 \leq 100$，所有 $U_i \leq 100$ 4. （21 分）所有 $U_i = 1$ 5. （20 分）$D_0 = 1$，所有 $T_i \in \{A, B, C\}$，所有 $U_i \leq 10$ 6. （30 分）无附加约束条件