AT_pakencamp_2022_day1_f Events Scheduling

パ研合宿の K 運営長はある一日に開催するイベントを何にするか決めたいです。 現在 $ N $ 個のイベントの候補があり、パ研合宿の参加者は $ M $ 人です。 $ i $ 個目のイベントの時間の長さは $ L_i $ です。また、 $ i $ 個目のイベントに対する $ j $ 人目の参加者の満足度は $ A_{i,j} $ です。 $ 1 $ 個以上の行うイベントを定めたとき、そのイベントの集合に対する良さは全ての人に対してのイベントの満足度の最大値の総和と定義されます。 一日の時間は限られているため、イベントの時間の長さの合計は $ D $ 以下である必要があります。このとき、行うイベントの集合の良さは最大でいくつになりますか？ ただし、イベントを一個も行うことができない場合はそのことを報告してください。

入力は以下の形式で標準入力から与えられます。 > $ 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` を出力してください。

### Sample Explanation 1 二つ目のイベントのみを行うのが最適です。 ### Sample Explanation 2 イベントを行うことができません。 ### Constraints - $ 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) $ - 入力は全て整数