天空中有一个星座，星座里面的星星被神秘的星线连接成了一个树状的结构，每个星星最多有两个子结点。每个星星都有一定的重量，标记摘第i标号（<6000）的星星重量为Si，摘去规则如下：
对于未摘出的星星，可以选择摘取它，再对其左(右)子女进行重复摘取（即如果第一次选择左子女，摘取顺序就应为：当前星星，左子女，左子女的左子女。。组成一条不间断的星串（可以在任意位置结束，不必到没有左子女为止）(右子女类比于左子女)）{当然摘掉的下次就不能再重复摘取了}，则该次摘取耗费的体力值为星串中所有星星的重量乘积；也可以单独摘取当前星星，耗费体力值即为星星重量值。
总耗费的体力值为每次摘取耗费体力值之和，现在小v想让你帮他设计一个方案，使得把所有星星拆成串时所耗费的体力值最小，你能帮他吗？
一个整数n，表示该星座中有n个星星
接下来n行，每行四个整数，分别表示为该星星的标号、摘该星星的体力值、其左子女的标号（如果没有则为0），其右子女的标号（同上）
一个整数s，表示所耗费的最小体力值。
5 1 1 2 5 5 4 0 0 3 5 0 0 2 3 3 4 4 7 0 0
19 Hint:对于图中的树，拆分方式为1和2（或5）成串，其他单独取 19=1*4+3+5+7 或1*3+4+5+7 当然，你不能取123，5，4，因为2是1的右子女，3是2的左子女