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())
Nlist = [[] for _ in range(N)]
Ncost = [0]*N
ans = -1

for i in range(N):
    cost_Nlist = list(map(int, input().split()))
    Ncost[i], Nlist[i] = cost_Nlist[0], cost_Nlist[1:]

for i in range(1 << N):
    total_cost = 0
    total_arugo = [0]*M
    for j in range(N):
        if(i >> j) % 2 == 0:
            continue
        total_cost += Ncost[j]
        for k in range(M):
            total_arugo[k] += Nlist[j][k]
    count = True
    for k in range(M):
        if total_arugo[k] < X:
            count = False
            break
    if count == False:
        continue
    if ans == -1:
        ans = total_cost
    else:
        ans = min(ans, total_cost)

print(ans)

Submission status: Accepted

Solution code:
# C Skill Up

def list_add(li1, li2):
  return [a+b for a, b in zip(li1, li2)]

N, M, X = map(int, input().split())
data = []
for n in range(N):
  data.append(list(map(int, input().split())))

ans = 10000000
for c in range(1 << N):
  x = [0] * M
  yen = 0
  for i, n in enumerate(format(c, f"{N}b")):
    if n == "1":
      yen += data[i][0]
      x = list_add(x, data[i][1:])
  for xm in x:
    if xm < X:
      break
  else:
    ans = min(ans, yen)
    
if ans == 10000000:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

min = float('inf')

for i in range(1<<n): # 1<<n == 2**n
    study = [0 for _ in range(m)]
    cost = 0

    for j in range(n):
        if i&(1<<j):
            cost += a[j][0]
            study = [study[k]+a[j][k+1] for k in range(m)]

    if(all([s >= x for s in study])):
        if min > cost:
            min = cost

if float('inf') > min:
    print(min)
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import product
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
A.insert(0,[0 for _ in range(M+1)])
flag = 0
for j in range(1,M+1):
    cnt = 0
    for i in range(1,N+1):
        cnt += A[i][j]
    if cnt<X:
        flag = 1
        break
if flag==1:
    cost = -1
else:
    cost = 10**7
    for x in product((0,1),repeat=N+1):
        if x[0]==0:
            flag1 = 0
            for j in range(1,M+1):
                cnt = 0
                for i in range(1,N+1):
                    if x[i]==1:
                        cnt += A[i][j]
                if cnt<X:
                    flag1=1
                    break
            if flag1==0:
                cnt = 0
                for i in range(1,N+1):
                    if x[i]==1:
                        cnt += A[i][0]
                cost = min(cost,cnt)
print(cost)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ans = 10000000
bs = []
for i in range(n):
    bs.append(tuple(map(int, input().split())))

for i in range(2**n):
    a = [0]*m
    c = 0
    for j in range(n):
        if (i>>j)&1:
            c += bs[j][0]
            for k in range(m):
                a[k]+=bs[j][k+1]
    if all([ai >= x for ai in a]):
        ans = min(ans,c)
if ans == 10000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
ans=10**18
for i in range(1<<n):
  rikai=[0]*m
  money=0
  for j in range(n):
    if i&(1<<j):
      money+=a[j][0]
      for k in range(1,m+1):
        rikai[k-1]+=a[j][k]
  ok=True
  for r in rikai:
    if r<x:
      ok=False
      break
  if ok:
    ans=min(money,ans)

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

import numpy as np
N, M, X = mapint()
CAs = [list(mapint()) for _ in range(N)]

ans = 10**18
flg = False
for i in range(1<<N):
    tar = np.array([0]*M)
    m = 0
    for j in range(N):
        if (i>>j)&1:
            c, *As = CAs[j]
            tar += np.array(As)
            m += c
    if all(tar>=X):
        ans = min(ans, m)
        flg = True

if flg:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

ans = float('inf')
for b in range(1<<N):
    arr = [0] * (M+1)
    for i in range(N):
        if b&(1<<i)==0: continue
        for j,v in enumerate(CA[i]):
            arr[j] += v
    if all(v >= X for v in arr[1:]):
        ans = min(ans,arr[0])
print(-1 if ans==float('inf') else ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
l = []
for i in range(n):
    tmp = list(map(int, input().split()))
    l.append(tmp)
inf = 1001001001001
ans = inf
for mask in range(1 << n):
    out = False
    pay = 0
    exp = [0 for _ in range(m)]
    for i in range(n):
        if (mask >> i & 1) == 1:
            pay += l[i][0]
            # 理解度計算
            for j in range(m):
                exp[j] += l[i][j + 1]
    # 理解度チェック
    for i in exp:
        if i < x:
            out = True
            break
    if not out:
        ans = min(ans, pay)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import copy as cp
import itertools as itr
import numpy as np

N,M,X=map(int, input().split())
c=np.array([list(input().split()) for l in range(N)],dtype=int)


v=list(itr.product(range(2),repeat=N))
ans=-1
for i in range(len(v)):
  ans2=0
  l=np.zeros(M,dtype=int)
  for j in range(N):        
    if v[i][j]==1:      
      for k in range(M):
        l[k]+=c[j][k+1]
      ans2+=c[j][0]
  if np.amin(l)>=X:  
    if ans==-1:
      ans=ans2
    else:
      ans=min(ans,ans2)
        
print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M, X = map(int, readline().split())
data = np.int32(read().rstrip().split()).reshape(N, M + 1)
C = data[:, 0]
A = data[:, 1:]

ans = 10**8
for choses in itertools.product([0, 1], repeat=N):
    row_mask = np.int32(choses) > 0
    if np.all(A[row_mask].sum(axis=0) >= X):
        ans = min(ans, C[row_mask].sum().item())

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

Submission status: Accepted

Solution code:
import numpy as np

n, m, x = map(int, input().split())
a = [None] * n
cost = 0
ans = float("inf")
for i in range(n):
    a[i] = list(map(int, input().split()))
for bit in range(1, 1 << n):
    ptn = []
    psum = [0]
    for i in range(n):
        if bit & 1 << i:
            ptn.append(a[i])
            psum = np.sum(ptn, axis=0)
    cost = psum[0]
    if np.min(psum[1:]) >= x:
        ans = min(ans, cost)
print(-1) if ans == float("inf") else print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
n,m,x = map(int, input().split())
ca = np.zeros((n,m+1))
for i in range(n):
    ca[i] = [int(i) for i in input().split()]

'''
N行を読む or 読まないで全探索する
itertools.productでTrue,Falseの全組み合わせリストを生成し、
Numpyのブールインデックス参照で本を選択する
答えは整数型じゃないといけない・・・
'''

p = itertools.product([True,False], repeat = n)
ans_l = []
for i in p:
    ca_cut = ca[i,:]
    if len(ca_cut) == 0: 
        continue
    ca_cut_sum = ca_cut.sum(axis=0)
    if all(ca_cut_sum[1:] >= x):
        ans_l.append(ca_cut_sum[0])
if len(ans_l) == 0:
    ans = -1
else:
    ans = min(ans_l)
print(int(ans))

Submission status: Accepted

Solution code:
import sys
N,M,X = map(int,input().split())
ls = []
for i in range(N):
    ls1 = list(map(int,input().split()))
    ls.append(list(ls1))
    ls1.clear()

ans=[]
for i in range(2**N):
    bag = []
    skill = [0]*M
    flg = True
    mon = 0
    for j in range(N):
        if i >> j & 1:
            bag.append(ls[j][0])
            mon += ls[j][0]
            for k in range(M):
                skill[k] += ls[j][k+1]
    if min(skill) >= X:
        ans.append(mon)
if len(ans) == 0:
    print("-1")
else:
    print(min(ans))

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
P = [list( map( int, input().split() ) ) for i in range(n)]
ca=np.array(P).reshape((n,m+1))
value= 10000000
for i in range(2**n):
  sum=np.zeros(m+1)
  for y in range(n):
    if list(bin(i >> y))[-1] == '1':
      sum += ca[-y-1,:]
    else:
      pass
  summ=sum[1:]
  if all(elm >= x for elm in summ) == True:
    if value==int(sum[0]):
      value=int(sum[0])
    else:
      value= min(int(sum[0]), value)
if value==10000000:
  print('-1')
else:
  print(value)

Submission status: Accepted

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

INF = 10 ** 9
ans = INF
for bit in range(1 << n):
    now = 0

    Q = [0]*m
    for i in range(n):
        if bit >> i & 1:
            now += P[i][0]
            for j in range(m):
                Q[j] += P[i][j+1]

    ok = 1
    for j in range(m):
        if Q[j] < x:
            ok = 0

    if ok == 1:
        ans = min(ans, now)

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

Submission status: Accepted

Solution code:
import itertools

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

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

p = list(itertools.product([0, 1], repeat=n))

lc = []
for i in range(2 ** n):
    list_sum_k = []
    for k in range(1, m+1):
        sum_c = 0
        sum_k = 0
        for j in range(n): #上からj行目を加算の対象とする
            if p[i][j] == 1: #j行目の和をk(1-m)について出す
                sum_c += l[j][0]
                sum_k += l[j][k]
        list_sum_k.append(sum_k)
    #print(sum_c)
    #print(list_sum_k)
    if all(k >= x for k in list_sum_k):
        #print('reach')
        lc.append(sum_c)
        #print(lc)

if not lc:
    print('-1')
else:
    print(min(lc))

Submission status: Accepted

Solution code:
def main():
    n,m,x = map(int,input().split())
    A = []
    ans = 10**9
    for i in range(n):
        tmp = [int(i) for i in input().split()]
        A.append(tmp)
    for i in range(2**n):
        arg = [0 for j in range(m+1)]
        cost = 0
        for j in range(n):
            if (i>>j)&1 ==1:
                cost += A[j][0]
                for k in range(1,m+1):
                    arg[k] += A[j][k]
        flag = True
        for k in range(1,m+1):
            if arg[k]<x:
                flag = False
                break
        if flag:
            ans = min(ans,cost)
    if ans==10**9:
        print('-1')
    else:
        print(ans)
main()

Submission status: Accepted

Solution code:
n ,m,x = map(int,input().split())
a = [None] * n
c = [None] * n
ans = float('inf')
for i in range(n):
    a[i] = list(map(int,input().split()))
    c[i] = a[i][0]
    a [i] = a[i][1:]
for i in range(2 ** n):
    rikai = [0] * m
    kane = 0
    bi = format(i,'012b')
    for j in range(n):
        if (i >> j)%2 == 1:
            kane += c[j]
            rikai = [rikai[f] + a[j][f] for f in range(m)]
    if all(rikai[f] >= x for f in range(m)):
        ans = min(ans,kane)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M, X) = map(int, input().split())
    A = np.zeros((N,M+1), dtype='int32')
    for i in range(N):
        A[i] = list(map(int, input().split()))
    
    A = A[np.argsort(A[:,0])]

    i = 0
    m = -1
    while i < 2**N:
        i += 1
        c = 0
        sum = np.zeros(M, dtype='int32')
        for j in range(N):
            if i & 2**j == 2**j:
                c += A[j][0]
                sum += A[j][1:]
        if np.all(sum >= X):
            m = c if m < 0 else min(m, c)
    
    print(m)
main()

Submission status: Accepted

Solution code:
def check(learn_total):
    for i in range(m):
        if learn_total[i] < x:
            return False
    return True
 
 
def calc_price(bit):
    price_total = 0  # 値段の合計
    learn_total = [0] * m  # 理解度
 
    for i in range(n):
        if (bit >> i) & 1:  # i桁目が0か1か見て、i番目を買うか買わないか判定します
            price_total += c[i]  # 買うので、i番目の値段を加算します
            learn = a[i]  # 「i番目の参考書を読んで増える、各アルゴリズムの理解度」のリストです
            for j, le in enumerate(learn):  # 理解度を足します。 enumerateを使うと、range(n)よりスマートです
                learn_total[j] += le
 
    # 条件を満たすか、check関数で確認します
    if check(learn_total):
        return price_total
    else:
        return INF
 
 
if __name__ == '__main__':
    INF = float("inf")
 
    n, m, x = list(map(int, input().split()))
 
    # 空のリストを作って、appendで追加していきます
    c = []  # 参考書の値段です
    a = []  # 各参考書に入る理解度です
 
    for i in range(n):
        c_temp, *a_temp = list(map(int, input().split()))  # こうすると、2つ目以降をリストで受け取れます
        c.append(c_temp)
        a.append(a_temp)
 
    ans = INF
 
    for bit in range(1 << n):
        price = calc_price(bit)  # 条件を満たすなら価格、満たさないならINFが返ってきます
        ans = min(ans, price)  # 答えを更新します
 
    if ans == 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:])
    
result = -1
"""
<< bit演算に関する演算子
左辺の値を右辺の値だけ左へシフトすることを意味する

https://www.javadrive.jp/python/num/index4.html

下記の場合、1からNまで2真数でシフトしていく感じ
"""

for i in range(1 << N):
    #初期化
    t = [0] * M
    c = 0
    #print(i)
    for j in range(N):
        #print(j)
        if(i >> j ) & 1 == 0 :
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

Submission status: Accepted

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

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

ans = -1

# 1冊目を買う/買わない、...、N冊目を買う/買わない
# 選び方は2**N通り
for i in range(1 << N):

    study = [0] * M
    cost = 0

    # 買った本にはビットが立っている
    # ex. 011 なら１、2冊目を買って3冊目を買わない
    for j in range(N):

        # j+1冊目を買った場合(j=0,1,...,N-1)
        if (i >> j) & 1:
            cost += C[j]

            # j+1冊目による理解度向上
            for m in range(M):
                study[m] += A[j][m]

    # 全ての理解度がX以上の場合
    if min(study) >= X:
        if ans == -1:
            ans = cost
        else:
            ans = min(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
import itertools as it
import numpy as np

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

for i in range (0, N):
	A.append(list(map(int, input().split())))

A = np.array(A)

L = list(it.product([0,1], repeat = N))

saishoucost = 100000000
Check = 0

for i in range (0, len(L)):
	D = np.array([0]*(M+1))
	Check = 0
	for j in range (0, N):
		if L[i][j] == 1:
			for k in range (0, M+1):
				D[k]+=A[j][k]
	for j in range (1, M+1):
		if D[j] < X:
			Check = 1
	if Check == 0:
		saishoucost = min(saishoucost, D[0])

if saishoucost == 100000000:
	print(-1)
else:
	print(saishoucost)

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
N,M,X=MI()
C=[]
A=[]
for i in range(N):
  L=LI()
  C.append(L[0])
  A.append(L[1:])
ans=-1
for i in range(1<<N):
  tmp=[0]*M
  cost=0
  for j in range(N):
    if 1&(i>>j):
      cost+=C[j]
      for m in range(M):
        tmp[m]+=A[j][m]
  if min(tmp)>=X:
    if ans==-1:
      ans=cost
    else:
      ans=min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
N,M,X=MI()
List=[]
for i in range(N):
  CA=LI()
  List.append(CA)
ans=-1
for i in range(1<<N):
  tmp=[0]*M
  cost=0
  for j in range(N):
    if 1&(i>>j):
      cost+=List[j][0]
      for k in range(M):
        tmp[k]+=List[j][k+1]
      if min(tmp)>=X:
        if ans==-1:
          ans=cost
        else:
          ans=min(ans,cost)
print(ans)

Submission status: Accepted

Solution code:

n,m,x=list(map(int,input().split()))
a=[]
l=[]
for i in range(n):
    p=list(map(int,input().split()))
    l.append(p)
for i in range(1,2**n):
    k=0
    ar=[0]*m
    for j in range(n):
        if (i>>j)&1==1:
            
            k+=l[j][0]
            for u in range(m):
                ar[u]+=l[j][u+1]
    
    if min(ar)>=x:
        a.append(k)
if len(a)>0:
    print(min(a))
else:
    print(-1)

Submission status: Accepted

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


def rikaido(lst):
    a = []
    for i in range(m):
        s = 0
        for j in range(len(lst)):
            s += lst[j][i]
        a.append(s)
    #print(a)
    return min(a)


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

ans = 10000000
for i in range(2 ** n):
    if i == 0:
        continue
    lst = []
    cost = 0
    for j in range(n):
        if (i >> j) & 1 == 1:
            lst.append(a[j])
            cost += c[j]
    #print(rikaido(lst))
    if rikaido(lst) >= x:
        ans = min(ans, cost)

if ans == 10000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
n,m,x=map(int,input().split())
li=np.array([list(map(int,input().split())) for i in range(n)])
ln=[j for j in range(n)]
ans=[]
for j in range(1,n+1):
    la=list(itertools.combinations(ln, j))
    for k in la:
      ls=np.zeros(m+1, dtype = int) 
      for l in range(len(k)):
        ls=ls+li[k[l]]
      lsp=[i for i in ls[1:] if i>=x]  
      if len(lsp)==m:
        ans.append(ls[0])
if ans==[]:
  print(-1)
else:
  print(min(ans))

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

N,M,X = list(map(int,input().split()))
CA = [ list(map(int,input().split())) for _ in range(N)]
bit = 2**N
cost = float('inf')

for bi in range(1,bit):
    tmp=[]
    for i in range(N):
        if bi & 1<<i:
            tmp.append(CA[i-1])
    tmp = np.array(tmp)        
    a = sum(tmp)
    if all( [a[j]>=X for j in range(1,M+1)]):
        cost = min(cost,a[0])
print( -1 if cost == float('inf') else cost)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
cost=[]
kekka=[]
res=[]
for _ in range(n):
    a=list(map(int, input().split()))
    cost+=[a[0]]
    kekka+=[a[1:]]
for i in range(2**n):
    sum=[0]*m
    money=0
    ok=1
    for j in range (n):
        if i>>j & 1:
            for k in range(m):
                sum[k]+=kekka[j][k]
            money+=cost[j]
    for l in sum:
        if l < x:ok=0
    if ok==1:res += [money]
print("-1" if res == [] else min(res))

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
ca = [list(map(int, input().split())) for i in range(n)]
ans = 10 ** 15
for i in range(2 ** n):
  rikai = [0] * m
  money = 0
  for j in range(n):
    if (i >> j) & 1:
      for k in range(m):
        rikai[k] += ca[j][k+1]
      money += ca[j][0]
  if min(rikai) >= x:
    ans = min(ans, money)
if ans == 10 ** 15:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
 
N,M,X = map(int,input().split())
ca = ([list(map(int,input().split())) for _ in range(N)])
ca = np.array(ca)
sumX = sum(ca)[1:]
sumcos = sum(ca)[0]
cost = sumcos
if sum(sumX>=X)<M:
    print(-1)
else:
    for j in range(1,N+1):
        for a in itertools.combinations(range(1,N+1),j):       
            x = sum(ca)[1:]
            fx = np.array([0]*M)
            c = sumcos
            for i in range(len(a)):
                x -= ca[a[i]-1][1:]
                c -= ca[a[i]-1][0]
                if sum(x>=X)<M:
                    break
                else:
                    cost = min(c,cost)
    print(cost)

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
import itertools

# 持っているビスケットを叩き、1枚増やす
# ビスケット A枚を 1円に交換する
# 1円をビスケット B枚に交換する
def main():
    n, m, x = input_list()
    books = {}
    contents = {}
    for i in range(n):
        c = input_list()
        books[i] = c[0]
        contents[i] = c[1:m+1]

    if n == 1:
        if sum(contents[0]) >= x:
            print(books[0])
        else:
            print(-1)
        exit()

    ans = []
    for v in itertools.product([0, 1], repeat=n):
        understands = [0] * m
        ok = [False] * m
        a = 0
        for i, vi in enumerate(v):
            if vi == 0:
                continue
            for index, val in enumerate(contents[i]):
                understands[index] += val
                if understands[index] >= x:
                    ok[index] = True
            a += books[i]
        if all(ok):
            ans.append(a)

    if len(ans) > 0:
        print(min(ans))
    else:
        print(-1)
        # a = 0
        # for vi in v:
        #     for index, val in enumerate(contents[vi]):
        #         understands[index] += val
        #         if understands[index] >= x:
        #             ok[index] = True
        #     a += books[vi]
        # if all(ok):
        #     ans.append(a)


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

def dfs(i, cost, A):
    if i == n-1:
        global ans
        if cost < ans and all([ai>=x for ai in A]):
            ans = cost
        return
    
    i += 1
    dfs(i, cost, A[:])
    dfs(i, cost+c[i], A[:]+a[i])

    
        
        

if __name__ == "__main__":
    n, m, x = map(int, input().split())
    c, a = [None]*n, np.array([None]*n)
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    ans = 10**20
    dfs(-1, 0, np.array([0]*m))
    if ans == 10**20:
        print(-1)
    else:
        print(ans)

Submission status: Accepted

Solution code:
from sys import exit
import numpy as np
#import copy
#from collections import deque



N,M,X =map(int, input().split())
C=[list(map(int, input().split())) for _ in range(N)]

tmp=float("inf")

for i in range(2**N):
    s=np.zeros(M+1)
    for j in range(N):
        if (i>>j)&1 :
            s+=C[j]
    if min(s[1:])>=X:
        tmp=min(s[0],tmp)

if tmp==float("inf"):
    tmp=-1
print(int(tmp))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ls = []
mi = 10**18
for i in range(n):
  ls.append(list(map(int,input().split())))
for i in range(2**n+1):
  cost = 0
  f = "{{:0{}b}}".format(n)
  now = f.format(i)
  understand = [0]*m
  for j in range(len(now)):
    if now[j] == "1":
      cost += ls[j][0]
      for k in range(m):
        understand[k] += ls[j][k+1]
  if min(understand) >= x:
    if mi > cost:
      mi = cost
if mi == 10**18:
  print(-1)
else:
  print(mi)

Submission status: Accepted

Solution code:
import sys
n, m, x = map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
mn=10**18
for mask in range(1<<n):
    l=[0]*(m+1)
    for i in range(n):
        if ((mask>>i)&1)==0:
            for j in range(m+1):
                l[j]+=c[i][j]
    count=0
    for k in range(1,m+1):
        if l[k]>=x:
            count+=1
    if count==m:
        mn=min(mn,l[0])

if mn==10**18:
    mn=-1
print(mn)

Submission status: Accepted

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

buy = list(itertools.product([0,1],repeat=n))

money = []

for i in range(len(buy)):
    algo = [0 for _ in range(m)]
    money_tmp = 0
    #j冊目の本
    for j in range(len(buy[i])):
        for k in range(m):
            algo[k] += book[j][k+1] * buy[i][j]
        money_tmp += book[j][0]*buy[i][j]
    #print(money_tmp)
    if min(algo) >= x:
        money.append(money_tmp)
        
if len(money) > 0:    
    print(min(money))
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def main():
    input = sys.stdin.readline
    n,m,x = map(int, input().split())
    c = []
    a = []
    for i in range(n):
        row = list(map(int, input().split()))
        c.append(row[0])
        a.append(row[1:])
    min_price = -1
    for nbit in range(1<<n): # red row bit h = 2なら 00 ~ 11 100(=2^2)　左ビットシフト 1 -> 100
        sum_price = 0
        sum_a = [0]*m
        for i in range(n):
            if nbit>>i & 1:
                for j in range(m):
                    sum_a[j] += a[i][j]
                sum_price += c[i]
        if sum_price == 0:
            continue
        elif all(value >= x for value in sum_a):
            if min_price == -1:
                min_price = sum_price
            elif sum_price < min_price:
                min_price = sum_price
    
    print(min_price)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
al = []
cl = []
for i in range(n):
    al.append(list(map(int, input().split())))
    cl.append(al[i].pop(0))

ans = []
for i in range(2**n):
    books = []
    for j in range(n):
        if i>>j & 1:
            books.append(j)

    a = True
    for alg in range(m):
        und = 0
        for b in books:
            und += al[b][alg]
        if und < x:
            a = False
            break
    if a:
        cost = 0
        for b in books:
            cost += cl[b]
        ans.append(cost)

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

Submission status: Accepted

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

books = [0] * n
for _ in range(n):
    books[_] = list(map(int, input().split()))

ans = -1
ans_list = []
for i in range(1<<n):
    money = 0
    cleared = 0
    level = [0]*m
    for j in range(n):
        if i>>j & 1:
            money += books[j][0]
            for book in range(m):
                level[book] += books[j][book+1]

    level.sort()
    if level[0] >= x:
        ans_list.append(money)

if len(ans_list) > 0:
    ans = min(ans_list)

print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int,input().split())
C = [list(map(int,input().split())) for x in range(N)] 
#最初だけ金額なことに注意
skill = [0]*M
flag = [0]*M    #スキルが身についてるかのフラグ
saisyou = 10**7
for p in range(2**N):
    for q in range(N):
        if p >> q & 1:      #q+1冊目の本について
            money += C[q][0]
            for r in range(M):  #各スキルの理解度追加
                skill[r] += C[q][r+1]
    for s in range(M):
        if skill[s] >= X:
            flag[s] = 1
    if 0 not in flag and money < saisyou:
        saisyou = money
    money = 0
    skill = [0]*M
    flag = [0]*M
if saisyou == 10**7:
    saisyou = -1
print(saisyou)

Submission status: Accepted

Solution code:
n,m,x=[int(x) for x in input().rstrip().split()]
l=[]
for i in range(n):
  ca=[int(x) for x in input().rstrip().split()]
  l.append(ca)

ans=float('inf')
for i in range(2**n):
  now=0
  under=[0]*m
  for j in range(n):
    if i>>j & 1:
      now+=l[j][0]
      for s in range(m):
        under[s]+=l[j][s+1]

  cnt=0
  for u in under:
    if x<=u:
      cnt+=1
  
  if cnt==m:
    ans=min(ans,now)

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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(N)]
ans = float('inf')
for mask in range(1,1<<N):
    tmp = [0]*M
    money = 0
    for i in range(N):
        if mask>>i & 1:
            for j in range(M):
                tmp[j]+=A[i][j+1]
            money+=A[i][0]
    if min(tmp)>=X:
        ans = min(ans,money)
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())
data = [list(map(int, input().split())) for _ in range(N)]
 
DEF_VAL = 99999999
min_cost = DEF_VAL
for rows in product([True, False], repeat=N):
    cost = 0
    x = [0] * M
    for i in range(N):    
        if rows[i]:
            cost += data[i][0]
            for c in range(M):
                x[c] += data[i][c+1]
    if min(x) >= X and cost < min_cost:
        min_cost = cost

if min_cost == DEF_VAL:
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
import itertools

n,m,x = map(int,input().split())
c = [0]*n
a = [[]]*n

for i in range(n) :
    d = list(map(int,input().split()))
    c[i] = d[0]
    a[i] = d[1:m+1]

max = 2**n
ans = 10**18
for i in range(max) :
    num = i
    cost = 0
    r = [0]*m
    check = 0
    for j in range(n) :
        f = num%2
        num = num//2
        if f == 0 :
            continue
        cost += c[j]
        r = [x+y for (x,y) in zip(r,a[j])]
    if all(elem >= x for elem in r) :
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
import numpy as np
n,m,x=map(int,input().split())
c=[]
a=[]
for i in range(n):
    d=list(map(int,input().split()))
    c.append(d[0])
    a.append(d[1:])
#print(c)
#print(a)

chk=np.zeros(m)
ans=10**9
for j in range(2**n):
    t=0
    s=np.zeros(m)
    for i in range(n):
        if j>>i&1:
            t+=c[i]
            for k in range(m):
                s[k]+=a[i][k]
            if min(s)>=x:
                ans=min(ans,t)

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