3644: Orz细菌-训练套题T15T3

3.Orz细菌(germ.pas/in/out)

【题目描述】老师最近正在研究一种新型细菌，名为ORZ细菌，这种细菌的生长方式很特别，它们只能通过吞噬同类才能长大。

两个orz细菌相遇后，较大的细菌会把较小的细菌吞噬（相同的话就看这两只细菌的RP了），吞噬后较大的细菌的体积会变为两只细菌体积之和，但这个过程会消耗能量，为了方便计算，消耗的能量近似为它们体积之和。

老师现在有n只细菌，他每回会从培养皿中取体积为前m小的细菌进行实验，让它们互相吞噬（残忍！）。实验的操作是这样的，老师将这m只细菌按体积大小放在一个环形的管道里，再给以细菌刺激，以加快或减慢相邻两只细菌相互吞噬的速度（我们认为这个加速度是无穷大的）。最后把幸存的那只细菌放回培养皿，再进行下次实验。由于细菌吞噬的能量要老师来提供，所以他希望经过k次实验后消耗的能量最少。输入数据保证，不会出现细菌不够的情况。

【输入格式】

  第一行有三个整数，分别为n，m，k ，第二行有n个整数，代表最初n个细菌的体积

   接下来的k行，每行m个整数，第i+2行的第j个数代表第i次实验的第j小的细菌放在哪个位置。例如m=5，第三行为，14235  代表最小的细菌放在第一个位置，第二小的细菌放在第四个位置…最大的细菌放在第五个位置（和第一个位置相邻）

【输出格式】只有一个整数，代表k次实验之后消耗的最小能量。

【数据规模】

  1<n<=100000,1<=m<=10,1<=k<=10000   数据保证结果不超过2^31

【输入样例1】

10 2 3

1 2 3 4 5 6 7 8 9 10

1 2

1 2

1 2

【输出样例1】

  18

【样例说明1】

   第一次是用体积为1 2的细菌  最终消耗能量3  变为一个体积为3的细菌

   第二次是用体积为3 3的细菌  最终消耗能量6  变为一个体积为6的细菌

   第三次是用体积为4 5的细菌  最终消耗能量9  变为一个体积为9的细菌

【输入样例2】

10 3 3

1 2 3 4 5 6 7 8 9 10

1 2 3

2 1 3

2 3 1

【输出样例2】

67