题目描述

TJU 1053浙江省2004组队赛第二试

修罗王挖到"神话时代"的宝藏后，发现宝藏里的科技源可以看成是一棵 技能树,一颗技能树的每个节点都是一项技能,要学会这项技能则需要耗费一定的 技能点数。

只有学会了某一项技能以后,才能继续学习它的后继技能。每项技能又有着 不同的级别,级别越高效果越好，而技能的升级也是需要耗费技能点数的。 现在修罗王已有一定的技能点数，他想旧能地利用这些技能点数来达到最 好的效果。因此他给所有的级别都打上了分，他认为效果越好的分数也越高。现 在他要你帮忙寻找一个分配技能点数的方案,使得分数总和最高。

输入格式

该题有多组测试数据。 每组测试数据第一行是一个整数$\red{n(1≤}$$\red{n≤}$$\red{20),}$表示所有不同技能的总数。

接下来依次给出$\red{n}$个不同技能的详细情况。

每个技能描述包括$\red{5}$行。

第一行是该技能的名称。

第$\red{2}$行是该技能在技能树中父技能的名称，名称为$\red{None }$则表示该技能不需 要任何的先修技能便能学习。

第$\red{3}$行是一个整数$\red{L(1≤}$$\red{L≤}$$\red{20),}$表示这项技能所能拥有的最高级别。

第$\red{4}$行共有$\red{L}$个整数,其中第$\red{I}$个整数表示从第$\red{I-1}$级升到第$\red{I}$级所需要的技 能点数,$\red{0}$级表示没有学习过。

第$\red{5}$行包括$\red{L}$个整数,其中第$\red{I}$个整数表示从第$\red{I-1}$级升级到第$\red{I}$级的效果评 分，分数不超过$\red{20}$。

在技能描述之后,共有两行,第$\red{1}$行是一个整数$\red{P,}$表示目前所拥有的技能点数。

接下来$\red{1}$行是$\red{N}$个整数，依次表示角色当前习得的技能级别,$\red{0}$表示还未学习。这里不会出现非法情况。

输出格式

每组测试数据只需输出最佳分配方案所得的分数总和。

样例

输入样例

Freezing Arrow
Ice Arrow
3
3 3 3
15 4 6
Ice Arrow
Cold Arrow
2
4 3
10 17
Cold Arrow
None
3
3 3 2
15 5 2
10
0 0 1

输出样例

42