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 を、 そうでなければ目標を達成するのに必要な金額の最小値を出力せよ。

入力例 1

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

出力例 1

120

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

入力例 2

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

出力例 2

-1

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

入力例 3

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

出力例 3

1067

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 1

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

Sample Output 1

120

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

Sample Input 2

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

Sample Output 2

-1

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

Sample Input 3

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 3

1067