/ 
実行時間制限: 4 sec / メモリ制限: 1024 MB
配点 : 475 点
問題文
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 社が目標を達成出来るか判定し、出来る場合は目標を達成するのに必要なコストの総和の最小値を求めてください。
制約
- 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)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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
4 3 5 5 3 0 2 3 1 2 3 3 2 4 0 1 0 1 4
出力例 1
9
1 個目と 3 個目と 4 個目の開発案を実行すると、それぞれのパラメーターが 3+2+0=5,0+4+1=5,2+0+4=6 で全て 5 以上となるため目標を達成できます。この場合コストの総和は 5 + 3 + 1 = 9 となります。
コストの総和 8 以下で目標を達成することは出来ません。よって答えは 9 です。
入力例 2
7 3 5 85 1 0 1 37 1 1 0 38 2 0 0 45 0 2 2 67 1 1 0 12 2 2 0 94 2 2 1
出力例 2
-1
どのようにしても目標を達成することは出来ません。よって -1 を出力します。
Score : 475 points
Problem Statement
AtCoder Inc. is planning to develop a product. The product has K parameters, whose values are currently all zero. The company aims to raise all parameter values to at least P.
There are N development plans. Executing the i-th development plan (1 \le i \le N) increases the value of the j-th parameter by A_{i,j} for every integer j such that 1 \le j \le K, at the cost of C_i.
A development plan cannot be executed more than once. Determine whether the company can achieve its goal, and if it can, find the minimum total cost required to achieve the goal.
Constraints
- 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)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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}
Output
If AtCoder Inc. can achieve its goal, print the minimum total cost required to achieve the goal; otherwise, print -1.
Sample Input 1
4 3 5 5 3 0 2 3 1 2 3 3 2 4 0 1 0 1 4
Sample Output 1
9
If you execute the first, third, and fourth development plans, each parameter will be 3+2+0=5,0+4+1=5,2+0+4=6, all of which are at least 5, so the goal is achieved. The total cost in this case is 5 + 3 + 1 = 9.
It is impossible to achieve the goal at a total cost of 8 or less. Thus, the answer is 9.
Sample Input 2
7 3 5 85 1 0 1 37 1 1 0 38 2 0 0 45 0 2 2 67 1 1 0 12 2 2 0 94 2 2 1
Sample Output 2
-1
You cannot achieve the goal no matter what you do. Thus, print -1.