#101374. [BZOJ 1374] [Baltic2003]Register

在编译器理论中，一个表达式是使用一棵树来表示的，其实根为运算符，子节点为分解出的子表达式。

在实际编译时，一个运算符只有当它所有子节点代表的表达式都求出以后，它才能够做相应的运算。

编译的时候，内存里有一种特殊的储存器「Register」，如果将得出的表达式储存到 「Register」 中，可以加快存取速度，但是由于「Register」数量有限，不能存入的表达式就只好用「主 Memory」来存储，这样的话就会造成时间上的浪费。

所以决定如何使用「Register」可以提高编译的效率。

具体的编译过程如下：

1. 对于一个非叶子节点，选任意一个子节点，进行运算（递归）；

2. 计算完以后，对于计算出的数值，可以选择存入「Register」或者存入「主 Memory」：

   • 若存入「Register，那么存取时间不计，但是在计算其他子节点表达式时，这个 「Register」 是不可用的；

   • 若存入「主 Memory」，存入需要 的时间，以后如果要调用这个值，还需要 的时间来调用。

3. 重新返回 1，直到所有的子节点表达式都处理完毕；

4. 这个时候，将所有存入「主 Memory」的数值从「主 Memory」中读入到「Register」中，一个数值占用一个「Register」；

5. 将所有「Register」中的数值按照根节点代表的运算符进行运算，得出结果；

6. 然后将所有使用到的「Register」清空。

所有的叶子节点代表的是数值，且必须从「主 Memory」中读入，每种运算符计算时使用的时间各有不同。

现要你决定编译的顺序和「Register」的使用，使得总运算时间最少。

第一行一个整数 ，表示「Register」的个数。

接下来每行一个数 ，表示根节点的子节点个数。

如果 ，那么 就是一个非叶子节点，代表 一个运算符，接下来一个数 代表这个运算符要使用的时间。

然后接下来就使用相同的格式来描述 的 个子节点。

一行一个数，表示最小的总运算时间。

样例输入

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

样例输出

47

样例说明

暂时未找到数据范围