CF1316E.Team Building

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.

FCB 俱乐部主席爱丽丝希望为即将举行的排球锦标赛组建一支队伍。该队伍需由 $p$ 名球员组成，每人担任 $p$ 个不同位置中的一个。她也深知观众支持的重要性，因此还希望从中选出 $k$ 人作为观众。

Byteland 共有 $n$ 人。爱丽丝需从这 $n$ 人中恰好选出 $p$ 名球员（每个位置恰好一人），并恰好选出 $k$ 名观众。她的最终目标是使俱乐部的总实力最大化。

第 $i$ 个人（$1 \le i \le n$）具有一个整数 $a_i$，表示若此人被选为观众，他将为俱乐部贡献的实力值。

对于每个人 $i$ 和每个位置 $j$（$1 \le j \le p$），爱丽丝已知 $s_{i,j}$ —— 表示若第 $i$ 个人被安排在第 $j$ 个位置上担任球员，他将为俱乐部贡献的实力值。

每个人最多只能被选中一次（即不能同时担任球员和观众，也不能在多个位置上重复担任球员）。且必须为每个位置恰好指定一名球员。

由于爱丽丝事务繁忙，她需要你帮她找出：通过最优地选择球员与观众，所能达到的俱乐部最大总实力。

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

第一行包含 $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}$）。

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

输出一个整数 ${res}$ —— 球队可能达到的最大实力值。

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

在第一个样例中，我们可以选择第 $1$ 个人担任第 $1$ 个位置的选手，而第 $2$ 和第 $3$ 个人作为观众。此时俱乐部的总实力等于 $a_{2}+a_{3}+s_{1,1}$。