F - Events Scheduling Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

パ研合宿の K 運営長はある一日に開催するイベントを何にするか決めたいです。

現在 N 個のイベントの候補があり、パ研合宿の参加者は M 人です。 i 個目のイベントの時間の長さは L_i です。また、i 個目のイベントに対する j 人目の参加者の満足度は A_{i,j} です。

1 個以上の行うイベントを定めたとき、そのイベントの集合に対する良さは全ての人に対してのイベントの満足度の最大値の総和と定義されます。

一日の時間は限られているため、イベントの時間の長さの合計は D 以下である必要があります。このとき、行うイベントの集合の良さは最大でいくつになりますか？

ただし、イベントを一個も行うことができない場合はそのことを報告してください。

制約

  • 1 \leq N,M \leq 18
  • 1 \leq D \leq 10^9
  • 1 \leq L_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq A_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
  • 入力は全て整数

入力

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

N M D
L_1 L_2 \cdots L_N
A_{1,1} A_{1,2}  \cdots A_{1,M}
A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,M}

出力

良さの最大値を 1 行に出力してください。イベントを一個も行うことができない場合は -1 を出力してください。

入力例 1

2 4 10
5 6
1 2 3 4
5 6 7 8

出力例 1

26

二つ目のイベントのみを行うのが最適です。

入力例 2

1 4 10
11
3 6 1 8

出力例 2

-1

イベントを行うことができません。

入力例 3

4 8 100
30 40 50 110
3 1 4 1 5 9 2 6
5 3 5 8 9 7 9 3
2 3 8 4 6 2 6 4
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

54