Problem:


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



Sample input:
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9


Sample output:
120

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c, a = [0] * n, [0] * n
for i in range(n):
    c[i], *a[i] = map(int, input().split())
l = []
b = [[a[j][i] for j in range(n)] for i in range(m)]
nums = [("0"*n + bin(i)[2:])[-n:] for i in range(1, 2 ** n)]
s = [sum(i) for i in b]

for i in nums:
    if min(sum(k[j]*int(i[j]) for j in range(len(i))) for k in b) >= x:
        l.append(sum(c[j]*int(i[j]) for j in range(len(i))))
print(min(l) if l else -1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())

ca=[list(map(int,input().split())) for _ in range(n)]

res=float('inf')

for i in range(2**n):
  sc=0
  a=[0]*m
  for j in range(n):
    if ((i >> j) & 1) :
      sc+=ca[j][0]
      for k in range(m):
        a[k]+=ca[j][k+1]
  if min(a)>=x:
    res=min(sc,res)

if res == float('inf'):
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
#Cbit全探索
n, m, x = map(int, input().split())
books = [list(map(int, input().split())) for i in range(n)]
ans = [0]*(m+1); ans[0] = 10**7  
for i in range(2**n):
    state = [0]*(m+1)
    for j in range(n):
        if (i >> j) & 1:
             for k in range(m+1):
                state[k] += books[n-1-j][k]
    for j in range(1,m+1):
        if state[j] < x:
            break
    else:
        if ans[0] >= state[0]:
            ans = state
if ans[0] == 10**7:
	print(-1)
else:
  print(ans[0])

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
bi_list = [bin(i)[2:] for i in range(2**n)] 
comb = [0] * (m+1)
comb[0] = 10**7
for i in bi_list:#本の選択パターン選択
    dig = len(i) 
    state = [0] * (m+1)
    for j in range(dig):#iから本の選択
        if i[dig-1-j] == '1':
            for k in range(m+1):#本の数値入力
                state[k] += l[n-1-j][k]
    for p in range(m):
        if state[m - p] < x:
            break
    else:
        if state[0] < comb[0]:
            comb = state
if comb[m] == 0:
    print(-1)
else:
    print(comb[0])

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, M, X = LI()
C = np.array([0 for i in range(N)])
A = np.array([[0 for i in range(M)] for j in range(N)])
for i in range(N):
    ca = LI()
    C[i] = ca[0]
    for j in range(M):
        A[i][j] = ca[1+j]


ans = mod
# 10進数のnをk進数のリストに変換
def n2kdigit(n,k):
    digits = []
    while n > 0:
        digits.append(n % k)
        n = n // k
    while len(digits) < N:
        digits.append(0)
    return digits

for i in range(2 ** N):
    skill = np.array([0 for i in range(M)])
    digit = np.array(n2kdigit(i, 2))
    for j in range(N):
        if digit[j]:
            skill += A[j]
    # print(skill)
    if np.all(skill >= X):
        ans = min(ans, sum(digit * C))
        # print(ans)

if ans == mod:
    print("-1")
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
skl = [[] for i in range(n)]
buy = [0]*n
for i in range(n):
    a = list(map(int,input().split()))
    buy[i] = a[0]
    skl[i] = a[1:]
    
INF = 114514191981036436433-4
ans = INF

for i in range(2**n):
    ls = [0]*n
    for j in range(n):
        if (i >> j) & 1:
            ls[j] = 1
        
    fl = True
    for j in range(m):
        gu = 0
        for k in range(n):
            gu += ls[k]*skl[k][j]
            
        if gu < x:
            fl = False
            break
            
    if fl:
        a = 0
        for i in range(n):
            a += buy[i]*ls[i]
            
        ans = min(ans,a)
        
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n,m,x = map(int,input().split())
seen = []
ans = 10**7

for i in range(n):
  seen.append(list(map(int,input().split())))
  
for i in range(2**n):
  temp = 0
  base = np.zeros(m)
  for j in range(n):
    if (i>>j)&1:
      for k in range(m):
        base[k] += seen[j][k+1]
      temp += seen[j][0]
 
  if (np.min(np.where(base >= x,1,0)) == 1) and (ans > temp):
    ans = temp
    
if ans == 10**7:
  ans = -1
  
print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())

C = []
A = []
for _ in range(n):
    t = list(map(int, input().split()))
    C.append(t[0])
    A.append(t[1:])
    
result = -1
for i in range(1 << n):
    t = [0] * m
    c = 0
    for j in range(n):
        if (i >> j) & 1 == 0:
            continue
        c += C[j]
        for k in range(m):
            t[k] += A[j][k]

    if all(l >= x for l in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

Submission status: Accepted

Solution code:
import sys
INF = 10**9
sys.setrecursionlimit(INF)


def main():
    n, m, x, *ca = map(int, open(0).read().split())
    ca = [ca[(1 + m) * _i:(1 + m) * (_i + 1)] for _i in range(n)]

    ans = INF
    # bit全探索
    for i in range(1 << n):
        tmp_ca = [0] * (m + 1)
        for j in range(n):
            if i >> j & 1:
                tmp_ca = [_i + _j for _i, _j in zip(ca[j], tmp_ca)]
        is_true = all([True if _i >= x else False for _i in tmp_ca[1:]])
        if is_true:
            if tmp_ca[0] < ans:
                ans = tmp_ca[0]

    if ans == INF:
        ans = -1

    print(ans)
    return(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N,M,X = [int(x) for x in input().split(' ')]

bookstore = []
total = float("inf")

for i in range(N):
    book = [int(x) for x in input().split(' ')]
    bookstore.append(book)


for n in range(2**N):
    c_cost = 0
    algos = [0] * M
    
    for i in range(n):
        if (1<<i)&n != 0:
            book = bookstore[i]
            c_cost += book[0]
            
            for x in range(1, M+1):
                algos[x-1] += book[x]
    
    valid = True
    for a in range(M):
        if algos[a] < X:
            valid = False
            break
    
    if valid == True:
        total = min(total, c_cost)

if total == float("inf"):
    print(-1)

else:
    print(total)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]
pass_list = []	#条件を満たした合計料金のリスト.最後に最小値を取得する。

for i in range(2**n):
  l_pic = [0]*(m+1)	#ピックアップしたbookによる効果（値段、スキルアップ量）の総和を見る。
  for j in range(n):
    if ((i >> j) & 1):	#ピックアップしたj番目について
      l_pic = [x+y for (x, y) in zip(l_pic, l[j])]
  if min(l_pic[1:]) >= x:
    pass_list.append(l_pic[0])

if len(pass_list) == 0:
  print(-1)
else:
  print(min(pass_list))

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
Cs = []
A = []
for i in range(N):
  As = list(map(int, input().split()))
  C = As.pop(0)
  Cs.append(C)
  A.append(As)
rs = []
for n in range(2**N):
  Bs = [0]*M
  r = 0
  for i in range(N):
    if (1<<i)&n != 0:
      r += Cs[i]
      As = A[i]
      for j in range(M):
        Bs[j] += As[j]
  if min(Bs) >= X:
    rs.append(r)
if len(rs) > 0:
  r = min(rs)
  print(r)
else:
  print(-1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
l=[]

for i in range(n):
    a=list(map(int,input().split()))
    l.append(a)
ans=99999999
for i in range(2 ** n):
    bag = []
    for j in range(n):  #bit全探索
        if ((i >> j) & 1): 
            bag.append(l[j])  
    skill=[0]*m
    enough=[0]*m #各スキルにつき、xを超えているかどうかを判断
    money=0
    for sub in bag:
        money+=sub[0]
        for kk in range(1,m+1):
            skill[kk-1]+=sub[kk]
            if skill[kk-1]>=x:
                enough[kk-1]+=1
    if 0 not in enough: #全てのスキルがxを超えていたら価格を計算
        if ans>money:
            ans=money#最低価格を下回っていたら更新
if ans==99999999: #初期値からの変更がなければ-1を、そうでなければ最低価格を出力
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
ca=[]
ans=-1
for i in range(n):
  ca.append(list(map(int,input().split())))
for i in range(1<<n):
  suma=[0]*(m+1)
  for j in range(n):
    if ((i>>j)&1):
      for k in range(m+1):
        suma[k]+=ca[j][k]
  chk=True
  for j in range(1,m+1):
    if suma[j]<x:
      chk=False
      break
  if chk and (ans==-1 or ans>suma[0]):
    ans=suma[0]
print(ans)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
numbers=[]
for _ in range(N):
  c=input().split()
  C=[int(a) for a in c]
  numbers.append(C)

skills=[]
for i in range(2 ** N):
  skill=[0 for _ in range(M+1)]
  for j in range(N):
    if ((i >> j) & 1):
      for k in range(M+1):
        skill[k]+=numbers[j][k]
  skills.append(skill)

del(skills[0])

answers=[]
for ability in skills:
  new_ability=ability[1:]
  necessary=[a for a in new_ability if a >= X]
  if len(necessary)==M:
    answers.append(ability[0])
if len(answers)==0:
  print(-1)
else:
  print(min(answers))

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
C = [0]*N
A = []
for i in range(N):
    temp = list(map(int,input().split()))
    C[i] = temp[0]
    A.append(temp[1::])


t = 10e15 
count = 0

array = []
def dfs(v,n,value):
    global t
    global count
    if n == N-1:
        if len(v) != 0 and all([i >= X for i in [sum(j) for j in zip(*v)]]):
            t=min(t,value)
        return 
    v.append(A[n+1])
    dfs(v,n+1,value+C[n+1])
    v.pop()
    dfs(v,n+1,value)

a =[]
dfs([],-1,0)

print(t if t!=10e15 else -1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = []
A = []
INF = float("inf")
ans = INF

for i in range(n):
    tmp = list(map(int, input().split()))
    c.append(tmp[0])
    A.append(tmp[1:])

for i in range(2**n):
  cost = 0
  skill = [0]*m
  for j in range(n):
     if ((i >> j) & 1) :
        cost += c[j]
        for k in range(m):
          skill[k] += A[j][k]
          if min(skill) >=x:
            ans = min(ans, cost)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
book_costs = []
book_skills = []
INF = float("inf")

for i in range(N):
    tmp = list(map(int, input().split()))
    book_costs.append(tmp[0])
    book_skills.append(tmp[1:])

res = INF

for i in range(2 ** N):
    cost = 0
    skills = [0] * M
    for j in range(N):
        if ((i >> j) & 1) :
            cost += book_costs[j]
            for k in range(M):
                skills[k] += book_skills[j][k]
    
    if min(skills) >= X:
        res = min(res, cost)

if res == INF:
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
li=[list(map(int,input().split())) for _ in range(N)]
ans=float("inf")
for i in range(2**N):
  PriceAbil=[0]*(M+1)
  for j in range(N):
    if (i>>j)&1:
      PriceAbil=[x+y for (x,y) in zip(PriceAbil,li[j])]
  if min(PriceAbil[1:])>=X:
    ans=min(ans,PriceAbil[0])
if ans==float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
li=[list(map(int,input().split())) for _ in range(N)]
ans=float("inf")
for i in range(2**N):
  price=0
  abil=[0]*M
  for j in range(N):
    if (i>>j)&1:
      price+=li[j][0]
      for k in range(1,M+1):
        abil[k-1]+=li[j][k]
  if min(abil)>=X:
    ans=min(ans,price)
if ans==float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = []
a = []
for i in range(n):
    tmp = list(map(int, input().split()))
    c.append(tmp[0])
    a.append(tmp[1:])

min_cost = -1

for i in range(2**n):
    cost = 0
    skills = [0] * m

    for j in range(n):
        if (i >> j) & 1:
            cost += c[j]
            skills = [skills[k] + a[j][k] for k in range(m)]

    if min(skills) >= x and (cost < min_cost or min_cost == -1):
        min_cost = cost

print(min_cost)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
li=[list(map(int,input().split())) for _ in range(N)]
ans=float("inf")
for i in range(2**N):
  price=0
  abil=[0]*M
  for j in range(N):
    if (i>>j)&1==1:
      #その本を購入する場合
      price+=li[j][0]
      #購入代金がpriceに加算される
      for k in range(1,M+1):
        abil[k-1]+=li[j][k]
        #購入したらその分の能力が各能力に加算される
  if min(abil)>=X:
    ans=min(ans,price)
if ans==float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
from itertools import product

n, m, x = map(int, input().split())
book = [[int(i) for i in input().split()] for j in range(n)]
cost = []

for p in product((0, 1), repeat=n):
    ex = [0] * m
    pre_cost = 0
    for i in range(n):
        if p[i] == 1:
            pre_cost += book[i][0]
            for j in range(m):
                ex[j] += book[i][j + 1]
    if min(ex) >= x:
        cost.append(pre_cost)
if cost:
    print(min(cost))
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(n)]
money = []

for i in range(2 ** n):
    value = [0] * (m+1)
    for j in range(n):
        if (i >> j) & 1:
            value = [value[k]+books[j][k] for k in range(m+1)]
            
    for l in range(m):
        if value[l+1] < x:
            break
        elif l == m-1:
            money.append(value[0])
            
if len(money) == 0:
    print('-1')
else:
    print(min(money))

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(N)]

ans = 10 ** 8

for bit in range(1<<N):
    rikaido = [0] * M
    cost = 0
    for i in range(N):
        mask = 1 << i
        if bit & mask:
            cost += ca[i][0]
            for j in range(1, M + 1):
                rikaido[j - 1] += ca[i][j]
    
    if min(rikaido) >= X:
        if cost < ans:
            ans = cost

if ans == 10 ** 8:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
books = []
for i in range(N):
    book = list(map(int, input().split()))
    books.append(book)

min_cost = -1
for i in range(2 ** N):
    cost = 0
    skills = [0] * M
    for j in range(N):
        if i & (2 ** j) != 0:
            cost += books[j][0]
            for s in range(M):
                skills[s] += books[j][s + 1]
    if min(skills) >= X and (min_cost < 0 or cost < min_cost):
        min_cost = cost

print(min_cost)

Submission status: Accepted

Solution code:
# bit全探索問題

N,M,X = map(int,input().split())
items = [list(map(int,input().split())) for _ in range(N)]
ans = -1
for i in range(1 << N):
    total = [0]*(M+1)
    for j in range(N):  
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            total = [x + y for (x, y) in zip(total, items[j])]
    # print(total)
    if all( k >= X for k in total[1:]) == True:
        if ans == -1:
            ans = total[0]
        else:
            ans = min(ans,total[0]) 
print(ans)

Submission status: Accepted

Solution code:
from itertools import product
N,M,X=map(int,input().split())
C=[]
A = [[] for _ in range(N)]
for i in range(N):
    inp=list(map(int,input().split()))
    C.append(inp[0])
    A[i]=inp[1:]
    
ans=float('inf')

for pattern in product([0,1],repeat=N):
    ms=[0]*M
    tmp_ans=0
    for i,p in enumerate(pattern):
        if p==0:
            continue
        tmp_ans += C[i]
        for j,q in enumerate(A[i]):
            ms[j] += q
    if all(m >= X for m in ms):
        ans = min(ans,tmp_ans)

if ans==float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())

C = []
A = []
for i in range(N):
    t = list(map(int, input().split()))
    C.append(t[0])
    A.append(t[1:])

alist = []

for i in range(1 << N):
    mlist = []
    slist = []
    plist = [0] * M # 0要素の数M個のリスト

    for j in range(N):

        if (i >> j) & 1 == 1:
            mlist.append(C[j])
            slist.append(A[j])

    for j in range(len(slist)):
        if len(slist)==1:
            plist = slist[j]
        else:
            plist = [a + b for a, b in zip(plist, slist[j])]

    if all((x >= X for x in plist)) == True:
        alist.append(sum(mlist))

if len(alist) != 0:
    print(min(alist))
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np
n, M, X = list(map(int, input().split()))
CA = []
A = []
for _ in range(n):
    L = list(map(int, input().split()))
    CA.append(L[:])
    
ans = np.zeros(M+1)
S = [0]*n
ANS = list()
def makeCombination():
    for i in range(0, n-1):
        S[i] = 0
    rec(0, ans)
def rec(i,ans):
    if i == n:
        if all(ans[1:] >= X) == True:
            ANS.append(ans[0])
        return
    rec(i + 1,ans)
    S[i] = 1
    ans = ans   + np.array(CA[i])
    rec(i + 1, ans)
    S[i] = 0
makeCombination()
ANS.sort()
if len(ANS) >= 1:
    print(int(ANS[0]))
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np


n, m, x = map(int, input().split())
l = [list(map(int, input().split())) for i in range(n)]

g = [np.array([0 for j in range(m+1)]) for i in range(2**n)]
min_c = 10**9

for i in range(2**n):
    tmp = list(bin(i))[2:]
    tmp.reverse()

    add_list = (np.array(tmp) == "1")
    for num, t in enumerate(add_list):
        if (t):
            g[i] += l[num]

for i in range(2**n):
    if (np.all(g[i][1:] >= x)):
        c = g[i][0]
        min_c = c if (c < min_c) else min_c

if min_c == 10**9:
    print(-1, end="")
else:
    print(min_c, end="")

Submission status: Accepted

Solution code:
from itertools import product
N, M, X = map(int, input().split())
C = []
A = [[] for _ in range(N)]
for i in range(N):
    inp = list(map(int, input().split()))
    c, a = inp[0], inp[1:]
    C.append(c)
    A[i] = a


ans = float('inf')
for pattern in product([0, 1], repeat=N):
    ms = [0] * M
    tmp_ans = 0

    for i, p in enumerate(pattern):
        if p == 0:
            continue
        tmp_ans += C[i]
        for j, a in enumerate(A[i]):
            ms[j] += a

    if all([m >= X for m in ms]):
        ans = min(ans, tmp_ans)

if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations

N, M, X = map(int, input().split())

items = []
calced = []

min_cost = float('inf')

for _ in range(N):
    items.append(list(map(int, input().split())))

for i in range(N):
    for combo in combinations(items, i+1):
        cost = 0
        exp = [0] * M
        mastered = True
        for c in combo:
            cost += c[0]
            for m in range(0,M):
                exp[m] += c[m+1]
        for m in range(M):
            if exp[m] < X:
                mastered = False
        if mastered:
            min_cost = min(min_cost, cost)


if min_cost == float('inf'):
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())

A=list(list(map(int,input().split())) for _ in range(N))

v=100000*100000
flag=1
for i in range(1<<N):
  price=0
  P=[0 for _ in range(M)]
  for j in range(N):
    if (i>>j)&1==1:
      for k in range(M):
        P[k]+=A[j][k+1]
      price+=A[j][0]
  judge=True      
  for l in range(M):
    if X>P[l]:
      judge=False
      break
  if judge:
    flag=0
    v=min(v,price)

if flag:
  v=-1

print(v)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import copy

def resolve():
    n, m, x = map(int, input().split())

    books = [list(map(int, input().split())) for i in range(n)]

    ans = 99999999

    # bit全探索
    # 本の数だけパターンを作成
    for i in range(1 << n):

        price = 0
        rikais = [0 for i in range(m)]

        # 本の数だけループ
        for j in range(n):

            # 値が1(購入)の場合
            if i & 1 << j:
                # 価格を加算
                price += books[j][0]
                # 理解度を加算
                for k in range(1, m+1):
                    rikais[k-1] += books[j][k]

            # すべてのアルゴリズムの理解度をX以上にできた場合
            if min(rikais) >= x:
                # 価格の最適解を更新
                ans = min(price, ans)

    # 価格を出力
    if ans is 99999999:
        print(-1)
    else:
        print(ans)







class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3 10
60 2 2 4
70 8 7 9
50 2 3 9"""
        output = """120"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3 3 10
100 3 1 4
100 1 5 9
100 2 6 5"""
        output = """-1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """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"""
        output = """1067"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function
from collections import defaultdict, Counter, deque
from future_builtins import ascii, filter, hex, map, oct, zip
from itertools import imap as map, izip as zip, permutations, combinations, combinations_with_replacement
from __builtin__ import xrange as range
from math import ceil, factorial, log,tan,pi,cos,sin,radians
from _continuation import continulet
from cStringIO import StringIO
from io import IOBase
import __pypy__
from bisect import bisect, insort, bisect_left, bisect_right
from fractions import Fraction
from functools import reduce
import string
import sys
import os
import re
inf = float('inf')
mod_ = int(1e9) + 7
mod = 998244353

def factors(n):
    from functools import reduce
    return set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def sieve(m):
    n=1
    primes = {}
    arr=set([])
    for i in range(2, int(m ** 0.5) + 1):
        a = n // i
        b = m // i
        for k in range(max(2, a), b + 1):
            c = i * k
            primes[c] = 1

    for i in range(max(n, 2), m + 1):
        if i not in primes:
            arr.add(i)

    return arr


class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n
 
    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a
 
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a != b:
            if self.size[a] < self.size[b]:
                a, b = b, a
 
            self.num_sets -= 1
            self.parent[b] = a
            self.size[a] += self.size[b]
 
    def set_size(self, a):
        return self.size[self.find(a)]
 
    def __len__(self):
        return self.num_sets

def isprime(t):
    for i in range(2,int(t**0.5)+1):
        if t%i==0:
            return False
    return True
def semiprime(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            if isprime(i) and isprime(x//i) and i!=x//i:
                return True
    return False



def main():
    n,m,x=map(int,input().split())
    arr=[]
    for i in range(n):
        book=list(map(int,input().split()))
        arr.append(book)
    # dest=[0]*m
    ans=[]
    for i in range(2**n):
        dest=[0]*(m+1)
        for j in range(n):
            if (i>>j)&1:
                for k in range(len(dest)):
                    dest[k]+=arr[j][k]
        # print(dest)
        if all(i>=x for i in dest[1:]):
            ans.append(dest[0])
    if len(ans)==0:
        print(-1)
    else:
        print(min(ans))




        

        
    




    



# region fastio

BUFSIZE = 8192

class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
books = [list(map(int, input().split())) for _ in range(n)]

ans = []

for i in range( 2 ** n ):
    total = [0] * (m + 1)
    for j in range(n):
        if (i >> j) & 1:
            total = [total[k] + books[j][k] for k in range(m+1)]

    over = True
    for j in range(1, m+1):
        if total[j] < x:
            over = False
    if over:
        ans.append(total[0])

if len(ans) > 0:
    print(min(ans))
else:
    print('-1')

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
books = [list(map(int, input().split())) for _ in range(n)]

ans = []

for i in range( 1 << n):
    total = [0] * (m + 1)
    for j in range(n):
        if (i >> j) & 1:
            total = [total[k] + books[j][k] for k in range(m+1)]

    over = True
    for j in range(1, m+1):
        if total[j] < x:
            over = False
    if over:
        ans.append(total[0])

if len(ans) > 0:
    print(min(ans))
else:
    print('-1')

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split()) #AtCoder Beginner Contest 167(C問題)
import numpy as np
Q=[]
list1 = [list(map(int,input().split())) for i in range(N)]
for i in range(1,2**len(list1)):
    list2 = []
    for j in range(len(list1)):
        if (i >> j) &1 == 1:
            list2.append(list1[j])
    Q.append(list2) #5~10行目でビット全探索を行い、変数Qに本の買い方の組合せを格納する。
R=[]

for q in range(0,len(Q)):
    Q[q]=np.array(Q[q])
    r=np.sum(Q[q], axis=0)
    R.append(r)
R=np.array(R) #10行目で得た組合せについて、本の値段とアルゴリズムの理解度の和をそれぞれ取り、行列にする。
S=R[:,1:] #アルゴリズムの理解度のみの行列を作る。
T=[]
for g in range(0,len(S)):
    if all(i >= X for i in S[g]): #Sのなかでアルゴリズムの理解度がすべてX以上の行のみ取り出す。
        T.append(R[g])
    else:
        T=T
if len(T)>0:
    T=np.array(T)
    T=T[T[:,0].argsort(), :] #本の値段の合計が安い順にする。
    print(T[0][0])
else:
    print(-1)
#AtCoder Beginner Contest 167(C問題) 以上

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
import numpy as np
Q=[]
list1 = [list(map(int,input().split())) for i in range(N)]
for i in range(1,2**len(list1)):  # 空集合を除く場合はrange(1, 2**len(list1))
    list2 = []
    for j in range(len(list1)):
        if (i >> j) &1 == 1:
            list2.append(list1[j])
    Q.append(list2)
R=[]

for q in range(0,len(Q)):
    Q[q]=np.array(Q[q])
    r=np.sum(Q[q], axis=0)
    R.append(r)
R=np.array(R) #17行目までで本の買い方を全て羅列。
S=R[:,1:] #18行目でアルゴリズムの理解度のみの行列を作る。
T=[]
for g in range(0,len(S)):
    if all(i >= X for i in S[g]): #Sのなかでアルゴリズムの理解度がすべてX以上の行のみ取り出す。
        T.append(R[g])
    else:
        T=T
if len(T)>0:
    T=np.array(T)
    T=T[T[:,0].argsort(), :] #本の値段の合計が安い順にする。
    print(T[0][0])
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())

c = []
for i in range(n):
    c.append([int(x) for x in input().split()])

min_cost = float('inf')

for i in range(2**n):
    cost = []
    ex = [0]*m
    for j in range(n):
        if (i>>j) & 1 == 1:
            cost.append(c[j][0])
            for k in range(1, m+1):
                ex[k-1] += c[j][k]
    flag = 1
    for l in range(len(ex)):
        if ex[l] < x:
            flag = 0
    if flag == 1:
        min_cost = min(min_cost, sum(cost))

if min_cost == float('inf'):
    print("-1")
else:
    print(min_cost)

Submission status: Accepted

Solution code:
N, M, X = map(int,input().split())
skill_book = []
for i in range(N):
    skill_book.append(list(map(int, input().split())))
box = []
flag = 1
for i in range(1 << N):
    total = [0] * (M + 1)
    for j in range(N):
        if (i >> j) & 1:
            total = [x + y for (x, y) in zip(total, skill_book[j])]
    over = 1
    for j in range(1, len(total)):
        if not (total[j] >= X):
            over = 0
    if over == 1 and len(total) > 0:
        box.append(total[0])
if len(box) > 0:
    print(min(box))
else:
    print('-1')