#P2654. 原核生物培养

原核生物培养

题目描述

W 教授最近正在研究一种原核生物,这种生物的生长方式很奇特,只能通过吃掉同类而生长。两个该种生物相遇,较大质量的会把较小的吃掉(相同的话就看 RP 了),吃掉后较大的生物的质量会变为两只原核生物重量之和,但这个过程会消耗酶,消耗的酶近似为它们重量之和。

W 教授现在有 nn 只原核生物,他每次会从培养皿中取重量最小的 mm 个生物进行实验,让它们自相残杀。

实验的操作是这样的,教授将这 mm 个原核生物按某种重量大小的顺序放在一个环形的管道里,然后给其中相邻两只原核生物酶,如此反复。最后把剩下的那只放回培养皿,接着进行下次实验。W 教授希望经过 kk 次实验后耗能最少。输入数据保证,不会出现生物不够的情况。

输入格式

第一行有三个整数,分别为 nn, mm, kk

第二行有 nn 个整数,代表最初 nn 个生物的重量。

接下来的 kk 行,每行 mm 个整数,第 i+2i+2 行的第 jj 个数代表第 ii 次实验的第 jj 小的生物放在哪个位置。例如 m=5m=5,第三行为,1423514235 代表最小的生物放在第一个位置,第二小的放第三个 \ldots 最大的放在第五个位置(和第一个位置相邻)。

输出格式

只有一个整数,代表 kk 次实验之后最小消耗酶的量。

10 2 3
1 2 3 4 5 6 7 8 9 10
1 2
1 2
1 2
18

提示

对于 100%100\% 的数据,1<n10001<n\leq 1000, 1m101\leq m\leq 10, 1k1001\leq k\leq 100。数据保证结果不超过 2312^{31}

样例解释:

第一次是用重量为 1,21, 2 消耗酶 33,变为一个重量 33

第二次是用重量为 3,33, 3 消耗酶 66,变为一个重量 66

第三次是用重量为 4,54, 5 消耗酶 99,变为一个重量 99

所以消耗总酶为 1818