2142: 宝典2第十一章技能树

【问题描述】技能树（skill）Tju1053浙江省2004组队赛第二试

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

只有学会了某一项技能以后，才能继续学习它的后继技能。每项技能又有着不同的级别，级别越高效果越好，而技能的升级也是需要耗费技能点数的。

现在修罗王已有一定的技能点数，他想尽可能地利用这些技能点数来达到最好的效果。因此他给所有的级别都打上了分，他认为效果越好的分数也越高。现在他要你帮忙寻找一个分配技能点数的方案，使得分数总和最高。

【输入格式】

该题有多组测试数据。

每组测试数据第一行是一个整数n（1≤n≤20），表示所有不同技能的总数。

接下来依次给出n个不同技能的详细情况。

每个技能描述包括5行。

第1行是该技能的名称。

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

第3行是一个整数L（1≤L≤20），表示这项技能所能拥有的最高级别。

第4行共有L个整数，其中第I个整数表示从第I－1级升到第I级所需要的技能点数（0级表示没有学习过）。

第5行包括L个整数，其中第I个整数表示从第I－1级升级到第I级的效果评分，分数不超过20。

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

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

【输出格式】

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

【输入样例】

3

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