原核生物培养

题目描述

W教授最近正在研究一种原核生物,这种生物的生长方式很奇特,只能通过吃掉同类而生长。两个该种生物相遇,较大质量的会把较小的吃掉(相同的话就看RP了),吃掉后较大的生物的质量会变为两只原核生物重量之和,但这个过程会消耗酶,消耗的酶近似为它们重量之和。 W教授现在有n只原核生物,他每次会从培养皿中取重量最小的m个生物进行实验,让它们自相残杀。 实验的操作是这样的,教授将这m个原核生物按某种重量大小的顺序放在一个环形的管道里,然后给其中相邻两只原核生物酶,如此反复。最后把剩下的那只放回培养皿,接着进行下次实验。W教授希望经过k次实验后耗能最少。输入数据保证,不会出现生物不够的情况。

输入输出格式

输入格式


第一行有三个整数,分别为n,m,k 第二行有n个整数,代表最初n个生物的重量 接下来的k行,每行m个整数,第i+2行的第j个数代表第i次实验的第j小的生物放在哪个位置。例如m=5,第三行为,14235 代表最小的生物放在第一个位置,第二小的放第四个…最大的放在第五个位置(和第一个位置相邻)

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

18

说明

1