现代计算机处理器拥有有限数量的寄存器（registers）——这是一种比主内存快得多的通用存储位置。执行计算的操作（例如加法、乘法等）要求其参数位于寄存器中，并将结果返回到寄存器中。
在本题中，我们考虑用于表达式求值的寄存器分配（register allocation）问题。在编译器内部，表达式被表示为一棵树。树的叶子节点对应于必须从主内存加载的值。树的中间（非叶子）节点对应于操作，每个中间节点的子节点数量与该操作的参数数量相同。显然，在执行操作之前，所有参数的值必须是可用的。
由于寄存器的数量有限，编译器必须决定将哪些中间结果保留在寄存器中（这些结果在需要时可以立即使用），以及将哪些中间结果存储到主内存中（这些结果在需要时必须重新加载）。改变一个操作的参数求值顺序也可能是有用的（这就是为什么大多数高级语言不保证任何特定的求值顺序）。
你的任务是编写一个程序，在给定一棵表达式树的情况下，找到总开销最小的寄存器分配方案和求值顺序。
输入格式
输入的第一行包含寄存器的数量 $N$（$1 \le N \le 100$）。
第二行包含两个整数：从主内存将值加载到寄存器的开销 $C_l$（$1 \le C_l \le 100$），以及将值从寄存器存储到主内存的开销 $C_s$（$1 \le C_s \le 100$）。
文件的其余部分描述了表达式树，从根节点开始：
- 第一行包含该节点的子节点数量 $K_x$（$0 \le K_x \le 10$ 且 $K_x \le N$）；
- 如果 $K_x = 0$，则这是一个叶子节点，该节点的描述结束；
如果 $K_x > 0$，则这是一个中间节点，并且：
- 下一行包含一个整数：该节点所代表的操作的开销 $C_x$（$1 \le C_x \le 100$）；
- 接下来按照相同的格式给出 $K_x$ 棵子树的描述。
节点按照它们在输入文件中出现的顺序从 $1$ 到 $M$ 进行编号。可以假设 $M \le 10\,000$。
输出格式
输出的第一行必须包含求值该表达式的最小总开销。
文件的其余部分必须为表达式树的每个中间节点包含一行。每行必须包含两个整数：第一个是要被求值的节点编号，第二个是 $1$（如果结果应保留在寄存器中）或 $0$（如果结果应存储到主内存中，此时 $C_s$ 的开销也将计入总求值开销）。
这些操作必须按照它们应该执行的顺序排列，以确保求值该表达式的总开销最小，且满足以下条件：
- 只有在某个节点的所有子节点都已被求值之后，该节点才能被求值；
- 要执行的操作中，所有不在寄存器中的参数都必须从主内存中加载（每个值的加载开销为 $C_l$）；
- 存放已执行操作参数的寄存器可以立即被重复使用，特别是用于存储该操作的结果。
如果存在多个开销最小的方案，输出其中任意一个即可。
样例
输入样例 1
2 3 2 2 10 2 15 0 0 2 5 0 0
输出样例 1
47 2 0 5 1 1 1
说明
下图说明了上述输入样例：两棵树都对应于同一个表达式树，其中左侧的树显示了中间节点的开销，右侧的树显示了节点的编号。
左图显示了中间节点的开销，右图显示了节点的编号。
上述输出样例中的求值方案总开销为：
$$(C_l + C_l + 15 + C_s) + (C_l + C_l + 5) + (C_l + 10) = 47$$
你将获得一个名为 REGSCHECK 的程序，用于验证 REGS.OUT 相对于 REGS.IN 的正确性（但不能验证其最优性），并会给出详细的错误信息。