時間制限 : sec, メモリ制限 : KB
Japanese

K: AOR イカちゃんの成績

問題

AOR イカちゃんは $N$ 回のレポートの点数のみで成績が決まる授業を受けている。 AOR イカちゃんは同じ授業を受けている友達が $M$ 人いて、自分が苦手なテーマのレポートは、そのテーマが得意な友達のレポートを写すことで、その友達と同じ点数を取ることができる。 ただし、他人のレポートを写していることを先生に気付かれてはいけないので、 $N$ 回のうち少なくとも $K$ 回は他人のレポートを写さず、自力でレポートを仕上げなくてはならない。 また、 AOR イカちゃんは友達に迷惑をかけたくないと思ったので友達 $i$ に対してレポートを写すのは $T_i$ 回以下にすることにした。 AOR イカちゃんが自力でレポートを仕上げたときの点数と、友達がレポートを仕上げた時の点数が与えられたときに、 AOR イカちゃんが取ることのできる合計点数の最大値を答えよ。

制約

  • $1 \le N \le 100$
  • $0 \le M \le 100$
  • $0 \le K \le N$
  • $0 \le a_i \le 100$
  • $0 \le b_{ij} \le 100$
  • $0 \le T_i \le N$

入力

入力は以下の形式で標準入力から与えられる。

$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 イカちゃんが取ることのできる合計点数の最大値を出力せよ。また、末尾に改行も出力せよ。

サンプル

入力例 1

3 2 2
50 65 70
80 100 80
90 65 45
1 1

出力例 1

225

AOR イカちゃんは 1 回だけ他人のレポートを写すことができるので、友達 2 の 1 つめのレポートを写すことで、 AOR イカちゃんは最高点数を取ることができる。

入力例 2

3 0 3
0 0 0

出力例 2

0

AOR イカちゃんには友達がいないため、レポートを写すことはできない。

Note

Commentary