Team Building

题意翻译

### 题目描述 你需要组建一支排球队。为了组织一支排球队,你需要为队伍里的$p$个不同的位置,从$n$个人中选出$p$个人,且每个位置上都恰好有一个人。另外还需要从剩下的人中选出恰好$k$个人作为观众。 对于第$i$个人,已知他作为观众时能为队伍增加$a_i$点力量,还有他在队伍的第$j$个位置上时能为队伍增加$s_{i,j}$点力量。请问这只排球队力量的最大值是多少? ### 输入格式 第一行三个正整数$n,p,k(2\leq n\leq 10^5,1\leq p\leq 7,1\leq k,k+p\leq n$. 第二行有$n$个正整数$a_i(1\leq a_i\leq 10^9)$. 接下来$n$行中,第$i$行有$p$个正整数,第$j$个表示$s_{i,j}(1\leq s_{i,j}\leq 10^9)$. ### 输出格式 一个正整数,表示组建的排球队的最大力量值。

题目描述

Alice, the president of club FCB, wants to build a team for the new volleyball tournament. The team should consist of $ p $ players playing in $ p $ different positions. She also recognizes the importance of audience support, so she wants to select $ k $ people as part of the audience. There are $ n $ people in Byteland. Alice needs to select exactly $ p $ players, one for each position, and exactly $ k $ members of the audience from this pool of $ n $ people. Her ultimate goal is to maximize the total strength of the club. The $ i $ -th of the $ n $ persons has an integer $ a_{i} $ associated with him — the strength he adds to the club if he is selected as a member of the audience. For each person $ i $ and for each position $ j $ , Alice knows $ s_{i, j} $ — the strength added by the $ i $ -th person to the club if he is selected to play in the $ j $ -th position. Each person can be selected at most once as a player or a member of the audience. You have to choose exactly one player for each position. Since Alice is busy, she needs you to help her find the maximum possible strength of the club that can be achieved by an optimal choice of players and the audience.

输入输出格式

输入格式


The first line contains $ 3 $ integers $ n,p,k $ ( $ 2 \leq n \leq 10^{5}, 1 \leq p \leq 7, 1 \le k, p+k \le n $ ). The second line contains $ n $ integers $ a_{1},a_{2},\ldots,a_{n} $ . ( $ 1 \leq a_{i} \leq 10^{9} $ ). The $ i $ -th of the next $ n $ lines contains $ p $ integers $ s_{i, 1}, s_{i, 2}, \dots, s_{i, p} $ . ( $ 1 \leq s_{i,j} \leq 10^{9} $ )

输出格式


Print a single integer $ {res} $ — the maximum possible strength of the club.

输入输出样例

输入样例 #1

4 1 2
1 16 10 3
18
19
13
15

输出样例 #1

44

输入样例 #2

6 2 3
78 93 9 17 13 78
80 97
30 52
26 17
56 68
60 36
84 55

输出样例 #2

377

输入样例 #3

3 2 1
500 498 564
100002 3
422332 2
232323 1

输出样例 #3

422899

说明

In the first sample, we can select person $ 1 $ to play in the $ 1 $ -st position and persons $ 2 $ and $ 3 $ as audience members. Then the total strength of the club will be equal to $ a_{2}+a_{3}+s_{1,1} $ .