AT_abc322_e [ABC322E] Product Development

[problemUrl]: https://atcoder.jp/contests/abc322/tasks/abc322_e AtCoder 社はある商品の開発をしようとしています。この商品には $ K $ 個のパラメーターがあり、現段階ではすべてのパラメーターの値が $ 0 $ です。AtCoder 社の目標は、パラメーターの値を全て $ P $ 以上にすることです。 ここで、$ N $ 個の開発案があります。$ i(1\ \le\ i\ \le\ N) $ 個目の開発案を実行すると、$ 1\ \le\ j\ \le\ K $ を満たす整数 $ j $ 全てに対して $ j $ 個目のパラメーターが $ A_{i,j} $ 上がりますが、この開発案を実行するにはコストが $ C_i $ かかります。 同じ開発案を $ 2 $ 回以上実行することは出来ません。AtCoder 社が目標を達成出来るか判定し、出来る場合は目標を達成するのに必要なコストの総和の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ P $ $ C_1 $ $ A_{1,1} $ $ A_{1,2} $ $ \dots $ $ A_{1,K} $ $ C_2 $ $ A_{2,1} $ $ A_{2,2} $ $ \dots $ $ A_{2,K} $ $ \dots $ $ C_N $ $ A_{N,1} $ $ A_{N,2} $ $ \dots $ $ A_{N,K} $

AtCoder 社が目標を達成出来るならば目標を達成するのに必要なコストの総和の最小値を、出来ないならば `-1` を出力せよ。

### 制約 - $ 1\ \le\ N\ \le\ 100 $ - $ 1\ \le\ K,P\ \le\ 5 $ - $ 0\ \le\ A_{i,j}\ \le\ P(1\ \le\ i\ \le\ N,1\ \le\ j\ \le\ K) $ - $ 1\ \le\ C_i\ \le\ 10^9(1\ \le\ i\ \le\ N) $ - 入力は全て整数 ### Sample Explanation 1 $ 1 $ 個目と $ 3 $ 個目と $ 4 $ 個目の開発案を実行すると、それぞれのパラメーターが $ 3+2+0=5,0+4+1=5,2+0+4=6 $ で全て $ 5 $ 以上となるため目標を達成できます。この場合コストの総和は $ 5\ +\ 3\ +\ 1\ =\ 9 $ となります。 コストの総和 $ 8 $ 以下で目標を達成することは出来ません。よって答えは $ 9 $ です。 ### Sample Explanation 2 どのようにしても目標を達成することは出来ません。よって `-1` を出力します。