#1126. 2130. 魔塔

2130. 魔塔

#2130. 魔塔

题目描述

魔塔是一款很流行的益智类小游戏。在游戏中,你可以控制主人公在魔塔中移动,走到怪兽面前便可以和怪兽来决斗,打败怪兽后可以得到金钱,并可以通过金钱来提高自己的攻击力、防御力、血量,从而变得更强大。然而,即便你拥有再高的攻击力、防御力,可以天下无敌,但一扇小小的门就可以阻止你无法前进。在游戏中,有红、黄、蓝三种颜色的门,并对应有红、黄、蓝三种颜色的钥匙。如果你想通过一扇门,需要消耗一把对应颜色的钥匙打开这扇门,如果你没有这种颜色的钥匙,便不能通过。现在你得到一款加强版的魔塔游戏:首先,门和钥匙的颜色不再是3种,而是n种,定为1~n号颜色。对于i号颜色的钥匙你有Ki把。并且之后你不会以任何形式得到任何颜色的钥匙。在你面前有三座n层的魔塔A、B、C。每座魔塔的入口处和相邻两层之间都会有一扇门。对于每座魔塔,恰好有n扇门,并且这n扇门的颜色恰好各不相同。其中,A魔塔中通往第i层的门颜色为DoorAi。(DoorBi、DoorCi的定义与DoorAi类似)在每座魔塔的每一层都有一定数量的怪兽,但这些怪兽根本打不过强大的你,你可以不费一滴血就秒杀这些怪兽,并得到杀死他们的金钱。我们已经为你统计好,消灭A魔塔第j层中所有的怪兽,可以得到的金钱数为GoldAi。(GoldBi、GoldCi的定义与GoldAi类似)现在,就请你来决策,如何运用这些钥匙,能得到最多的金钱,并告诉我们最多能获得多少金钱。

输入格式

第一行一个字符(A~F),表示数据类型(在下面数据规模中有详细介绍)第二行一个整数m,表示有几组测试数据。之后给出m组数据,对于每组数据有九行: 第一行一个整数n,表示魔塔层数。第二行一个数列Ki。第三行至第五行,每行一个数列,分别为DoorA、DoorB、DoorC。第六行至第八行,每行一个数列,分别为GoldA、GoldB、GoldC。第九行为一个空行。

输出格式

输出应包含m行,每行一个正整数,为最大能获得的金钱数。

样例

样例输入

A  

2  

5  

1 2 1 1 2  

1 2 3 4 5  

2 4 3 5 1  

5 4 3 2 1  

1 1 1 1 5  

1 2 2 3 3  

1 2 1 1 1  

  

5  

1 2 1 1 2  

1 2 3 4 5  

2 4 3 5 1  

5 4 3 2 1  

1 1 1 1 50  

1 2 2 3 3  

1 2 1 1 1  

样例输出

12  

56  

【样例说明】  

对于第一个数据:  

1 2 3 4 5     第一个魔塔不用钥匙,能得到0金钱;  

2 4 3 5 1)    第二个魔塔用1、2、3、4、5号钥匙,得到11金钱;  

5)4 3 2 1     第三个魔塔用5号钥匙,得到1金钱;  

最多可得到12金钱。  

对于第二个数据:  

1 2 3 4 5)    第一个魔塔用1、2、3、4、5号钥匙,能得到54金钱;  

2)4 3 5 1     第二个魔塔用2号钥匙,得到1金钱;  

5)4 3 2 1     第三个魔塔用5号钥匙,得到1金钱;  

最多可得到56金钱。  

【数据规模】  

对于全部数据,满足:  

1<=m<=10;  

1<=n<=100000;  

1<=Ki<=2;  

0<= GoldAi、 GoldBi、 GoldCi <=2000;  

DoorA、DoorB、DoorC为三个1到n的排列。  

数据共分为六类:A、B、C、D、E、F,他们分别有各自的特征:  

A类数据占10%,保证n<=100。  

B类数据占10%,保证n<=1000。  

C类数据占10%,保证GoldCi=0,即第三座塔中没有任何金钱。  

D类数据占20%,保证Ki=1,即每种钥匙你都只有一把。  

E类数据占30%,保证DoorA、DoorB、DoorC三个1到n的排列为随机产生的数列。  

F类数据占20%,没有其他特征。  

数据范围与提示