填空题

信服招聘

Question

今年参加深信服校招的同学非常优秀，很多同学身兼多种技能，可以胜任几种不同岗位(比如开发、算法、网络攻防等)。

 

有n位同学应聘m种不同岗位，每个岗位要招聘k个人。经过评估，每位同学对于每个岗位都有一个能力值，表示对该岗位的擅长程度。用A[i][j]表示第i位同学对于第j个岗位的能力值。若第i位同学确实被安排在第j种岗位，那他将创造A[i][j]这么大的价值。

 

为了让尽可能多的同学发挥本领，信服君决定请你来给同学们安排岗位。让所有岗位所招聘的同学的创造的总价值最大。需要说明的是，一个同学不能同时安排在多个岗位，每个岗位最多安排k个同学。

 

输入描述： 第一行一个正整数T(T<=100)，表示有T场招聘。

接下来T组测试数据，

每组测试数据第一行三个正整数n，m，k，表示有n位同学应聘m种不同岗位，每个岗位要招聘k个人。(1<=n<=50，1<=m<=10，1<=k<=10，m*k<=n)

接下来一个n*m的矩阵A,其中第i行第j列表示第i位同学对于第j个岗位的能力值A[i][j]。 (0<=A[i][j]<=100)

有50%的数据满足n<=10。输入样例： 2 2 2 1 99 98 98 99 3 2 1 99 98 96 92 94 94 输出描述： 输出T行，每行一个正整数，表示该场招聘到的所有人员经最优分配后能够创造的最大价值。输出样例 198 194