← 返回题目列表

Codeforces · 1316/E

E. 团队建设

中文机器翻译题面 查看原题

FCB 俱乐部主席 Alice 想要为新的排球锦标赛组建一支球队。球队应该由$$$p$$$ 不同位置的球员组成。她还认识到观众支持的重要性,因此她想选择 $$$k$$$ 人作为观众的一部分。

Byteland 有 $$$n$$$ 人。 Alice 需要从 $$$n$$$ 人群中准确选择 $$$p$$$ 玩家,每个位置一名,并准确选择 $$$k$$$ 名观众。她的最终目标是最大化俱乐部的整体实力。

$$$n$$$ 个人中的第 $$$i$$$ 拥有一个与他相关的整数 $$$a_{i}$$$ — 如果他被选为观众成员,则他为俱乐部增加的力量。

对于每个人 $$$i$$$ 和每个位置 $$$j$$$,Alice 知道 $$$s_{i, j}$$$ — 如果他被选为第 $$$j$$$ 位置,则第 $$$i$$$ 人为俱乐部增加的力量。

每个人最多可以被选一次作为玩家或观众。你必须为每个位置选择一名球员。

由于爱丽丝很忙,她需要你帮助她找到俱乐部的最大可能实力,这可以通过球员和观众的最佳选择来实现。

输入

第一行包含 $$$3$$$ 整数 $$$n,p,k$$$ ($$$2 \leq n \leq 10^{5}, 1 \leq p \leq 7, 1 \le k, p+k \le n$$$)。

第二行包含 $$$n$$$ 整数 $$$a_{1},a_{2},\ldots,a_{n}$$$。 ($$$1 \leq a_{i} \leq 10^{9}$$$)。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含 $$$p$$$ 整数 $$$s_{i, 1}, s_{i, 2}, \dots, s_{i, p}$$$。 ($$$1 \leq s_{i,j} \leq 10^{9}$$$)

输出

打印一个整数 $$${res}$$$ — 球杆的最大可能强度。

示例

输入 #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

注意

在第一个示例中,我们可以选择人物 $$$1$$$ 在 $$$1$$$-st 位置进行游戏,并选择人物 $$$2$$$ 和 $$$3$$$ 作为观众。那么俱乐部的总实力将等于$$$a_{2}+a_{3}+s_{1,1}$$$。