话说由于余震的威胁,JDC和全校同学地震当晚只能睡在操场上。JDC睡在操场上,迷迷糊糊就进入了梦想,他做了这样一个梦:
JW老师最近正在研究一种新型细菌,名为ORZ细菌,这种细菌的生长方式很特别,它们只能通过吞噬同类才能长大(那它们是怎么产生的呢?)。两个orz细菌相遇后,较大的细菌会把较小的细菌吞噬(相同的话就看这两只细菌的RP了),吞噬后较大的细菌的体积会变为两只细菌体积之和,但这个过程会消耗能量,为了方便计算,消耗的能量近似为它们体积之和。
JW老师现在有n只细菌,他每回会从培养皿中取体积为前m小的细菌进行实验,让它们互相吞噬(残忍!)。实验的操作是这样的,JW老师将这m只细菌按体积大小放在一个环形的管道里,再给以细菌刺激,以加快或减慢相邻两只细菌相互吞噬的速度(我们认为这个加速度是无穷大的)。最后把幸存的那只细菌放回培养皿,再进行下次实验。由于细菌吞噬的能量要JW老师来提供,所以他希望经过k次实验后消耗的能量最少。输入数据保证,不会出现细菌不够的情况。
数据规模
1<n<=100000,1<=m<=10,1<=k<=10000
数据保证结果不超过2^31
样例说明(不用输出)
第一次是用体积为1 2的细菌 最终消耗能量3 变为一个体积为3的细菌
第二次是用体积为3 3的细菌 最终消耗能量6 变为一个体积为6的细菌
第三次是用体积为4 5的细菌 最终消耗能量9 变为一个体积为9的细菌
所以消耗总能量为18
第一行有三个整数,分别为n,m,k
第二行有n个整数,代表最初n个细菌的体积
接下来的k行,每行m个整数,第i+2行的第j个数代表第i次实验的第j小的细菌放在哪个位置。例如m=5,第三行为,14235 代表最小的细菌放在第一个位置,第二小的细菌放在第四个位置…最大的细菌放在第五个位置(和第一个位置相邻)
只有一个整数,代表k次实验之后消耗的最小能量。