题目描述

小明作为 $\mathtt{ANGAO}$ 排球俱乐部的主席，想要为即将到来的排球比赛建立一个团队。

这个团队应该由 $p$ 名球员组成，打 $p$ 个不同的位置。他也意识到观众支持的重要性，所以他想要选择 $k$ 个人作为观众（球员和观众共同组成了这个团队）。

在 $\mathtt{ANGAO}$ 排球俱乐部一共有 $n$ 个会员。小明需要从这 $n$ 个会员中精确选择 $p$ 名球员（每个位置一个），并且精确选择 $k$ 名观众成员。他的最终目标是最大化俱乐部的总实力。

第 $i$ 个人有一个与他相关的整数 $a_{i}$ $\Rightarrow$ $a_i$ 表示如果第 $i$ 个人被选为观众的一员，他将为俱乐部增加的实力。

对于每个人 $i$ 和每个位置 $j$，小明知道$s_{i, j}$ $\Rightarrow$ $s_{i, j}$ 表示如果第 $i$ 个人被选为打第 $j$ 个位置的球员，他将为俱乐部增加的实力。

每个人最多可以被选为球员或观众的一员（即一个人不能在成为球员的同时担当观众）。你必须为每个位置选择一个球员。

由于小明很忙，他需要你帮助他找到选择球员和观众以达到的俱乐部的最大可能实力。

输入格式

第一行包含三个整数 $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}, \ldots, s_{i, p}$ ($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中，我们可以选择第$1$个人打第$1$个位置，选择第$2$和第$3$个人作为观众。然后俱乐部的总实力将等于$a_{2}+a_{3}+s_{1,1}$。