Description

Professor W is studying a kind of prokaryote whose growth is peculiar: it can grow only by devouring its conspecifics. When two such organisms meet, the heavier one eats the lighter one (if they have the same weight, it is decided by “RP”, i.e., luck). After eating, the survivor’s weight becomes the sum of the two weights, and the amount of enzyme consumed is approximately equal to the sum of their weights.

Professor W currently has $n$ prokaryotes. Each time, he takes the $m$ lightest organisms from the petri dish for an experiment and lets them fight each other.

The operation is as follows: he places these $m$ organisms around a circular tube in some order according to their weights, then repeatedly chooses a pair of adjacent organisms and supplies enzyme to them; after they merge, the survivor’s weight becomes the sum of the two, and the enzyme consumed equals that sum. Repeat this until only one organism remains. The remaining one is put back into the petri dish, and the next experiment begins. Professor W wants the total enzyme consumption to be minimized after $k$ experiments. The input guarantees that there will never be a shortage of organisms.

Input Format

The first line contains three integers $n$, $m$, $k$.

The second line contains $n$ integers, the initial weights of the $n$ organisms.

The next $k$ lines each contain $m$ integers. In the $(i+2)$-th line, the $j$-th number denotes the position where the $j$-th lightest organism in the $i$-th experiment is placed. For example, if $m=5$ and the line is $14235$, it means the smallest organism is placed in position 1, the second smallest in position 4, the third smallest in position 2, the fourth smallest in position 3, and the largest in position 5 (which is adjacent to position 1).

Output Format

Output a single integer, the minimal total amount of enzyme consumed after $k$ experiments.

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

18

Hint

Constraints: For $100\%$ of the testdata, $1 < n \leq 1000$, $1 \leq m \leq 10$, $1 \leq k \leq 100$. It is guaranteed that the result does not exceed $2^{31}$.

Sample explanation: In the first experiment, use weights $1, 2$, consuming $3$ enzyme and merging into weight $3$. In the second experiment, use weights $3, 3$, consuming $6$ enzyme and merging into weight $6$. In the third experiment, use weights $4, 5$, consuming $9$ enzyme and merging into weight $9$. Therefore, the total enzyme consumption is $18$.

Translated by ChatGPT 5