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}$$$。