题目描述

小Y想组建一支排球队。

为了组织一支排球队，小Y需要从 $n$ 个人中选出 $p$ 个人，安排到 $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)$。

输出格式

一行一个正整数，表示组建的排球队的最大力量值。

4 1 2
1 16 10 3
18
19
13
15

44

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

377

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

422899

说明/提示

在样例 1 中，我们可以选择将第一个人放置在第一个位置，第二个人和第三个人作为观众，于是队伍的力量值为 $s_{1,1}+a_2+a_3=44$。可以证明不存在更优的解法。