#215624. [BalticOI 2003] Register Allocation (Day 2)

Modern computer processors have a limited number of registers --- general purpose storage locations that are substantially faster than the main memory. The operations that perform computations (e.g. addition, multiplication, etc.) expect their arguments in the registers and return the result in a register.

In this task we consider the problem of register allocation for expression evaluation. Inside a compiler, an expression is represented as a tree. Leaf nodes of the tree correspond to values that have to be loaded from the main memory. Intermediate (non-leaf) nodes of the tree correspond to the operations and each of them has as many children as there are arguments to the operation. Obviously, the values of all arguments must be available before an operation can be performed.

Because there is only a limited number of registers, the compiler has to decide which of the intermediate results to keep in the registers (these are available immediately when they are needed) and which ones to store into the main memory (these must be loaded back when they are needed). It may also be useful to change the order of evaluation of the arguments for an operation (this is why most high-level languages do not guarantee any particular order).

Your task is to write a program that, given an expression tree, finds the register allocation plan and evaluation order with the minimal total cost.

The first line of the input contains the number of registers, (). The second line contains two integers: the cost of loading a value from the main memory into a register, (), and the cost of storing a value from a register into the main memory, (). The rest of the input describes the expression tree, starting from the root node:

• the first line contains the number of children of the node, ( and );
• if , this is a leaf node and the description is over;
• if , this is an intermediate node, and:
  • the next line contains one integer: the cost of the operation that the node represents, ();
  • this is followed by the descriptions of the subtrees according to the same scheme.

The nodes are numbered from to in the order in which they appear in the input. It can be assumed that .

The first line of output must contain the minimal cost of evaluating the expression. The rest of the ouput must contain one line for each intermediate node of the expression tree. Each line must contain two integers: the first is the number of the node to be evaluated, the second is if the result should be kept in a register, or if it should be stored into the main memory (with the cost also added to the total cost of evaluation).

The operations must be listed in the order in which they should be performed to ensure that the total cost of evaluating the expression is the least possible, under the following conditions:

• a node can only be evaluated after all its children have been evaluated;
• all arguments of an operation to be performed that are not in the registers have to be loaded from the main memory (with the cost per value);
• registers containing the arguments of the operation performed can be immediately reused, in particular for storing the result of the operation.

If there are several plans with minimal cost, output any one of them.

样例输入 1

2
3 2
2
10
2
15
0
0
2
5
0
0

样例输出 1

47
2 0
5 1
1 1

The figure below illustrates the input above: both trees correspond to the expression tree, whereas the tree on the left shows the costs of the intermediate nodes and the tree on the right shows the numbering of the nodes.

The cost of the evaluation plan in the output above is .

You will be given a program which verifies the correctness (but not optimality) of the with respect to the and gives informative error messages.