C - Skill Up

Contest Duration: 2020-05-10(Sun) 12:00 - 2020-05-10(Sun) 13:40 (local time) (100 minutes) Back to Home

C - Skill Up Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $300$ 点

問題文

競技プログラミングを始めた高橋くんは、学びたいアルゴリズムが $M$ 個あります。最初、各アルゴリズムの理解度は $0$ です。

高橋くんが書店に行くと、 $N$ 冊の参考書が売っていました。 $i$ 番目の参考書 ( $1\leq i\leq N$ ) は $C_i$ 円で売られていて、購入して読むことで、各 $j$ ( $1\leq j\leq M$ ) について $j$ 番目のアルゴリズムの理解度が $A_{i,j}$ 上がります。また、それ以外の方法で理解度を上げることはできません。

高橋くんの目標は $M$ 個すべてのアルゴリズムの理解度を $X$ 以上にすることです。高橋くんが目標を達成することが可能か判定し、可能な場合は目標を達成するのに必要な金額の最小値を計算してください。

制約

入力はすべて整数
$1\leq N, M\leq 12$
$1\leq X\leq 10^5$
$1\leq C_i \leq 10^5$
$0\leq A_{i, j} \leq 10^5$

入力

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

 $N$   $M$   $X$ 
 $C_1$   $A_{1,1}$   $A_{1,2}$   $\cdots$   $A_{1,M}$ 
 $C_2$   $A_{2,1}$   $A_{2,2}$   $\cdots$   $A_{2,M}$ 
 $\vdots$ 
 $C_N$   $A_{N,1}$   $A_{N,2}$   $\cdots$   $A_{N,M}$

出力

高橋くんが目標を達成できないならば -1 を、そうでなければ目標を達成するのに必要な金額の最小値を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

$2, 3$ 番目の参考書を購入すると $120$ 円ですべてのアルゴリズムの理解度を $10$ 以上にすることができ、これが最小値です。

入力例 2Copy

Copy

出力例 2Copy

Copy

-1

すべての参考書を購入しても $1$ つ目のアルゴリズムの理解度が $10$ に達しません。

入力例 3Copy

Copy

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

出力例 3Copy

Copy

Score : $300$ points

Problem

Takahashi, who is a novice in competitive programming, wants to learn $M$ algorithms. Initially, his understanding level of each of the $M$ algorithms is $0$ .

Takahashi is visiting a bookstore, where he finds $N$ books on algorithms. The $i$ -th book ( $1\leq i\leq N$ ) is sold for $C_i$ yen (the currency of Japan). If he buys and reads it, his understanding level of the $j$ -th algorithm will increase by $A_{i,j}$ for each $j$ ( $1\leq j\leq M$ ). There is no other way to increase the understanding levels of the algorithms.

Takahashi's objective is to make his understanding levels of all the $M$ algorithms $X$ or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.

Constraints

All values in input are integers.
$1\leq N, M\leq 12$
$1\leq X\leq 10^5$
$1\leq C_i \leq 10^5$
$0\leq A_{i, j} \leq 10^5$

Input

Input is given from Standard Input in the following format:

 $N$   $M$   $X$ 
 $C_1$   $A_{1,1}$   $A_{1,2}$   $\cdots$   $A_{1,M}$ 
 $C_2$   $A_{2,1}$   $A_{2,2}$   $\cdots$   $A_{2,M}$ 
 $\vdots$ 
 $C_N$   $A_{N,1}$   $A_{N,2}$   $\cdots$   $A_{N,M}$

Output

If the objective is not achievable, print -1; otherwise, print the minimum amount of money needed to achieve it.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Buying the second and third books makes his understanding levels of all the algorithms $10$ or higher, at the minimum cost possible.

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

-1

Buying all the books is still not enough to make his understanding levels of all the algorithms $10$ or higher.

Sample Input 3Copy

Copy

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

Sample Output 3Copy

Copy