2753. [济南集训 2017] 涂颜色

【题目描述】

从前有一个$n$行$m$列的网格。

现在有$S$种颜色,第$i$种颜色可以涂$a_i$ 格,保证

$\sum a_i = n * m$。

需要你对这个网格图进行着色,你必须按照从上到下,每一行内从左到右

的顺序进行着色,并且在用完一种颜色前你不能换颜色(当然颜色的使用顺序

是随意的) 。

每个相邻的相同色块可以获得1分,问在给定的规则下进行着色所能获得的

最高分是多少。

多组数据。

【输入格式】

第一行一个整数T 表示数据组数。

对于每组数据,第一行三个整数n, m, S表示网格的大小和颜色的数量。

之后一行S个数,第i个数表示第i种颜色可以涂的格数。

【输出格式】

对于每组数据一个数$ans$,表示能获得的最高分。

【样例输入】

2
3 3 4
1 2 2 4
4 2 4
1 2 2 3

【样例输出】

5
4

【样例解释】

第一组数据

1 2 2
3 3 4
4 4 4

第二组数据

1 4
4 4
2 2 
3 3

【数据规模与约定】

对于 $30\%$的数据,$1 ≤ n, S ≤ 10, 1 ≤ m ≤ 2$

对于 $60\%$的数据,$1 ≤ n, S ≤ 1000, 1 ≤ m ≤ 3$

对于 $100\%$的数据,$1 ≤ n, S ≤ 100000, 1 ≤ m ≤ 4, a i ≥ 1, T ≤ 10$

【来源】

清北学堂济南NOIP集训二试$T_1$