Description

在编译器理论中，一个表达式是使用一棵树来表示的，其实根为运算符，子节点为分解出的子表达式。在实际编译时，一个运算符只有当它所有子节点代表的表达式都求出以后，它才能够做相应的运算。 编译的时候，内存里有一种特殊的储存器“Register”，如果将得出的表达式储存到Register中，可以加快存取速度，但是由于Register数量有限，不能存入的表达式就只好用主Memory来存储，这样的话就会造成时间上的浪费。所以决定如何使用Register可以提高编译的效率。 具体的编译过程如下： 1． 对于一个非叶子节点，选任意一个子节点，进行运算（递归） 2． 计算完以后，对于计算出的数值，可以选择存入Register或者存入主Memory。 a) 若存入Register，那么存取时间不计，但是在计算其他子节点表达式时，这个Register是不可用的。 b) 若存入主Memory，存入需要Cs的时间，以后如果要调用这个值，还需要Cl的时间来调用。 3．重新返回1，直到所有的子节点表达式都处理完毕。 4．这个时候，将所有存入主Memory的数值从主Memory中读入到Register中，一个数值占用一个Register。 5．将所有Register中的数值按照根节点代表的运算符进行运算，得出结果。 6．然后将所有使用到的Register清空。 所有的叶子节点代表的是数值，且必须从主Memory中读入，每种运算符计算时使用的时间各有不同。现要你决定编译的顺序和Register的使用，使得总运算时间最少。

Input

N（Register个数） Cl,Cs 一个数Kx，表示根节点的子节点个数。 如果Kx>0，那么x就是一个非叶子节点，代表一个运算符，接下来一个数Cx代表这个运算符要使用的时间。 然后接下来就使用相同的格式来描述x的Kx个子节点。

Output

总计算时间

Samples

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

47

Limitation