AOR イカちゃんは $N$ 回のレポートの点数のみで成績が決まる授業を受けている。 AOR イカちゃんは同じ授業を受けている友達が $M$ 人いて、自分が苦手なテーマのレポートは、そのテーマが得意な友達のレポートを写すことで、その友達と同じ点数を取ることができる。 ただし、他人のレポートを写していることを先生に気付かれてはいけないので、 $N$ 回のうち少なくとも $K$ 回は他人のレポートを写さず、自力でレポートを仕上げなくてはならない。 また、 AOR イカちゃんは友達に迷惑をかけたくないと思ったので友達 $i$ に対してレポートを写すのは $T_i$ 回以下にすることにした。 AOR イカちゃんが自力でレポートを仕上げたときの点数と、友達がレポートを仕上げた時の点数が与えられたときに、 AOR イカちゃんが取ることのできる合計点数の最大値を答えよ。
入力は以下の形式で標準入力から与えられる。
$N \ M \ K$
$a_1 \ \cdots \ a_N$
$b_{11} \ \cdots \ b_{1N}$
$\vdots$
$b_{M1} \ \cdots \ b_{MN}$
$T_1 \ \cdots \ T_M$
$a_i$ はAORイカちゃんが $i$ 番目のレポートを仕上げた時の点数を、$b_{ij}$ は友達 $i$ が $j$ 番目のレポートを仕上げた時の点数を表す。
AOR イカちゃんが取ることのできる合計点数の最大値を出力せよ。また、末尾に改行も出力せよ。
3 2 2 50 65 70 80 100 80 90 65 45 1 1
225
AOR イカちゃんは 1 回だけ他人のレポートを写すことができるので、友達 2 の 1 つめのレポートを写すことで、 AOR イカちゃんは最高点数を取ることができる。
3 0 3 0 0 0
0
AOR イカちゃんには友達がいないため、レポートを写すことはできない。