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: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc167/tasks/abc167_c C - Skill Up
import numpy as np
from itertools import combinations
N,M,X=list(map(int,input().split()))
book_dict={}
for i in range(M):
    book_dict[i] = list(map(int,input().split()))

answer = 10**5*12+1
for i in range(M,0,-1):
    for v in combinations(book_dict.keys(), i):
        search_book = list(map(lambda x:book_dict[x],list(v)))
        sum_search_book = np.array(np.sum(search_book,axis = 0))
        if (np.count_nonzero(sum_search_book[1:] >= X) == N) and sum_search_book[0] < answer:
            answer = sum_search_book[0]
                                                                                 
           
        
        
    
if answer == 10**5*12+1:
    answer = -1

print(answer)

Submission status: Runtime Error

Solution code:
#https://atcoder.jp/contests/abc167/tasks/abc167_c C - Skill Up
import numpy as np
from itertools import combinations
N,M,X=list(map(int,input().split()))
book_dict={}
for i in range(M):
    book_dict[i] = list(map(int,input().split()))

answer = 10**5*12+1
for i in range(M,0,-1):
    for v in combinations(book_dict.keys(), i):
        search_book = list(map(lambda x:book_dict[x],list(v)))
        sum_search_book = np.array(np.sum(search_book,axis = 0))
        if (np.count_nonzero(sum_search_book[1:] >= X) == N) and sum_search_book[0] < answer:
            answer = sum_search_book[0]
                                                                                 
           
        
        
    

print(answer)

Submission status: Runtime Error

Solution code:
from itertools import combinations
n, m, x = map(int, input().split())
ca = list(map(int, input().split()))

ans = 10**9
for i in range(1,n+1):
  for j in combinations(ca, i):
    s = [0]*(m+1)
    for k in j:
      for l in range(m+1):
        s[l] += k[l]
    if min(s[1:]) <= x:
      ans += min(ans, s[0])
if ans == 10**9:
  print(-1)
else:
  print(ans)

Submission status: Runtime Error

Solution code:
import itertools
n,m,x=map(in,input().split())
l=[list(map(int,input().split())) for i in range(n)]
costl=[]
for p in itertools.product([0,1],n):
  al=[0]*m
  cost=0
  for i in range(n):
    if p[i]==1:
      cost+=l[i][0]
      for j in range(1,m):
        al[j-1]+=l[i][j]
  if all(mm>=x for mm in m):
    costl.append(cost)
print(min(cost))

Submission status: Runtime Error

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

c = [[]]*N
a = [[[]]*M]*N

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


ans = 10**7

for i in range(2 ** N):
    price = 0
    intelligence = [0 for _ in range(M)]
    for j in range(N):
        if ((i >> j) & 1):
            price += c[j]
            for k in range(M):
                intelligence[k] += a[j][k]
    flag = 1
    for k in range(M):
        if intelligence[k] < X:
            flag = 0
    if flag == 1:
        ans = min(ans,price)

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

Submission status: Runtime Error

Solution code:
A, B, C, K = list(map(int, input().split()))

if A >= K:
    print(K)
elif (A+B) >= K:
    print(A)
else:
    print(2*A+B-K)

Submission status: Runtime Error

Solution code:
N,M,X = map(int,input().split())
listA=[]
while True:
    try:
        listA.append(list(map(int,input().split())))
    except:
        break;

min_cost = 10**10000000
for i in range(2**N):
  bi2 = bin(N)[2:].zfill(N)
  skill = [0] * M
  cost = 0
  for n in range(N):
    if bi2[n] == 1:
      cost += listA[n][0]
      for m in range(M):
        skill[m] += listA[n][m+1]
  if all(skill) > X and cost < min_cost: min_cost = cost

if min_cost = 10**10000000:print(-1)
else:print(min_cost)

Submission status: Runtime Error

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

#ca = [map(int, input().split()) for _ in range(n)]
#ca = [input().split() for l in range(n)]
import sys
ca = [[int(c) for c in l.split()] for l in sys.stdin]
#c, a = [list(i) for i in zip(*ca)]
#print(ca)
#print(ca[0][0])
c=[]
a=[]
for l in range(n):
    c.append(ca[l][0])
#print(c)

for l in range(n):
    del ca[l][0]
#print(ca)
a=ca

INF = float('INF')
min_cost = INF
 
def dfs(i, cost, learn):
    if i == n:
        if min(learn) >= x:
            return cost
        else:
            return INF
    else:
        new_learn = [X + Y for (X, Y) in zip(a[i], learn)]
        cost = min(dfs(i + 1, cost, learn), dfs(i + 1, cost + C[i], new_learn))
        return cost
 
min_cost = dfs(0, 0, [0] * m)
 
if min_cost == INF:
    print(-1)
else:
    print(min_cost)

Submission status: Runtime Error

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


cmin=12*10**5+1
for bit in range(2**N):
    A=[0]*M
    c=0
    for j in range(N):
        if (bit>>j)&1:
            c+=l[j][0]
            A=[x+y for (x,y) in zip(A, l[j][1:])]
    if min(A) >= X:
        cmin=min(cmin,c)

if cmin!=12*10**5+1:
    print(cmin)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
now=1
count=0
a=0
l=[1]
b=0
c=0
while a==0and count<K:
    now=A[now-1]
    count+=1
    if now in l:
        a=1
    else:
        l.append(now)
b=l.index(now)
c=count-b+1
if count==K:
    print(now)
else:
    n=int((K-b)/c)
    ncount=0
    while ncount <n:
        now=A[now-1]
        ncount+=1
    print(now)

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=np.zeros(N+1)
a=list(map(int,input().split()))
for i in range(N+1):
  A[i]=a[i]
v=0
j=0
k=0
B=np.zeros(N+1)
for i in range(N+1):
  B[i]=N-i
for i in reversed(range(0, N+1)):
  j+=A[i]/(2**i)
  if i==N:
    k=A[i]
  else:
    k=min(k+A[i],2**i-np.sum(A[0:i]*(2**(B[0:i]-(N-i)))))
  v+=k

if j>1:
  print(-1)
else:
  print(int(v))

Submission status: Runtime Error

Solution code:
import numpy as np

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

ca = []
for _ in range(N):
  ca.append( list(map(int, input().split())))
ca.sort(key=lambda x:-x[0])
ca = np.array(ca)
#
ans = 10000000
skill = [0]*(M+1)


def DFS(n,skill):
  global ans
  if skill[0] >= ans:
    return
  if min(skill[1:]) >= X:
    ans = min(ans, skill[0])
    return
  if n >= N:
    return
  DFS(n+1,skill)
  skill = skill + ca[n]
  DFS(n+1,s)
  skill = skill - ca[n]
  return
#

DFS(0,skill)
if ans == 10000000:
  print(-1)
else:
  print(ans)
#

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import numpy as np
nmx = input().split(" ")
n = int(nmx[0])
m = int(nmx[1])
x = int(nmx[2])
a = []
c = []
tanka = []
noryoku = [0] * m

r = 0

for i in range(n):
  text = input().split(" ")
  price = int(text[0])
  c.append(price)
  a.append([int(text[i]) for i in range(1, m + 1)])
  tanka.append([price / int(text[i]) for i in range(1, m + 1)])

a = np.array(a)
# price = np.array(price)

while len(tanka) > 0:
  min_i = np.argmin(tanka, axis=0)
  min_v = np.min(tanka, axis=0)
  index = min_i[np.argmax(min_v)]
  # print(min_i)

  # for j in range(m):
  #   noryoku[j] += a[min_i][j]

  noryoku = [noryoku[j] +  a[index][j] for j in range(m)]
  r += c[index]

  if all(v >= x for v in noryoku):
    print(r)
    break

  tanka = np.delete(tanka, index, 0)
  a = np.delete(a, index, 0)
  c.pop(index)

else:
  print(-1)

Submission status: Runtime Error

Solution code:
def CanIGetEnoughSkills(SkillPoints,M,X):
    for _ in range(M):
        if SkillPoints[_]<X:
            return False
        else:
            pass
    return True


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

BookCost=[]
GetSkillPoints=[]
for i in range (N):
    BookCost.append(books[i][0])
    GetSkillPoints.append(books[i][1:])

temp_cost=10**9

for Cart in range (2**len(GetSkillPoints)):
    TotalCost=0
    SkillPoints=[0]*M

    for book in range(len(GetSkillPoints)):
        if (Cart>>book)&1==0:
            continue
        TotalCost+= BookCost[book]
        for skillelement in range(M):
            SkillPoints[skillelement]+=GetSkillPoints[book][skillelement]

    # print(TotalCost,SkillPoints)
    if CanIGetEnoughSkills(SkillPoints,M,X)== True:
        temp_cost=min(temp_cost,TotalCost)

Answer=temp_cost
if Answer==10**9:
    Answer=-1
    
print(Answer)

Submission status: Runtime Error

Solution code:
# ABC 167 C
N,M,X = map(int,input().split())
C =[]
for m in range(N):
    C.append([int(i) for i in input().split()])
C.sort(key=lambda x:x[0])

from itertools import combinations
import numpy as np

ans = 10**5 +1

for m in range(1,M+1):
    P=list(combinations(C,m))
    tmp =np.sum(P,axis=1)
    if ans < tmp[0,0]:
        print(ans)
        exit()
    elif min(tmp[0,1:])>=X and ans > tmp[0,0]:
        ans = tmp[0,0]


if min(tmp[0,1:])<X:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
n,m,x=map(int,input().split())
clis=[]
alis=[]
for _ in range(n):
  tu=list(map(int,input().split()))
  clis.append(tu[0])
  alis.append(tu[1:])


ma_c=[]
for i in range(2**n):
  bag=[]
  price=0
  for j in range(n):
    if ((i>>j)&1):
      price+=clis[j]
      bag.append(alis[j])
  pac=[0]*m
  for t in range(len(bag)):
    for k in range(m):
        pac[k]+=bag[t][k]
  if all([pac[t]>=x for t in range(m)]):
    ma_c.append(price)

print(min(ma_c))

Submission status: Runtime Error

Solution code:
import numpy as np

def func(ans, b_list, a_list, c_list, k, x):
    if k == 0:
        b_list = np.asarray(b_list)
        x_list = np.dot(b_list, a_list)
        if np.all(x_list >=x):
            return np.inner(c_list, b_list)
        else:
            return ans

    ans = min(ans , func(ans , b_list + [1], a_list, c_list, k-1, x))
    ans = min(ans, func(ans, b_list + [0], a_list, c_list, k-1, x))
    return ans

def main():
    n, m, x = map(int, input().split())
    c_list = []
    a_list = []
    for i in range(0,n):
        c, *a = map(int, input().split())
        c_list.append(c)
        a_list.append(a)

    ans = float("inf")
    c_list = np.asarray(c_list)
    a_list = np.asarray(a_list)
    ans = min(ans, func(ans, [1], a_list, c_list, n - 1, x))
    ans = min(ans, func(ans, [0], a_list, c_list, n - 1, x))
    if ans ==float("inf"):
        print(-1)
    else:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

for i in range(2**N):
  temp = []
  job = [0] * M
  for s in range(N):
    if (i>>s)&1:
      temp.append(s)
      for j in range(M):
        job[j] += item[s][j+1]
  for s in range(len(job)):
    if job[s]<X:
      break
  else:
    ans = 0
    for s in temp:
      ans += item[s][0]
    bag.append(ans)
print(min(bag) if len(bag)>=1 else -1)

Submission status: Runtime Error

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[m-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: Runtime Error

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]
      a+=ca[j][1:]
  if min(a)>=x:
    res=min (sc,res)

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

Submission status: Runtime Error

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

c = []
a = []
for i in range(N):
  t = list(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(x >= X for x in t):
        if result == -1:
            result = C
        else:
            result = min(result, C)
print(result)

Submission status: Runtime Error

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のチェックを行う
            h = [x + y for (x, y) in zip(total, items[j])]
    # print(total)
    if all( k >= X for k in h[1:]) == True:
        if ans == -1:
            ans = h[0]
        else:
            ans = min(ans,total[0]) 
print(ans)

Submission status: Runtime Error

Solution code:
# bit全探索問題

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

Submission status: Runtime Error

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:])

# N, M, X = 3, 3, 10
# C = [60,70,50]
# A = [[2,2,4],[8,7,9],[2,3,9]]

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])
    # print(i,mlist,slist,len(slist))

    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))
        # print(i,plist)

print(min(alist))

Submission status: Runtime Error

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(ANS[0])
else:
    print(-1)

Submission status: Runtime Error

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:
        #print(S)
        print(ans)
        print(ans[1:] >= X)
        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(ANS[0])
else:
    print(-1)

Submission status: Runtime Error

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 << M):
    total = [0] * (M + 1)
    for j in range(M):
        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])

print(min(box))

Submission status: Runtime Error

Solution code:
import numpy as np
n , m , x = map(int,input().split())
understand_list = [list(map(int,input().split()))]
for _ in range(n-1):
    understand_list.append(list(map(int,input().split())))

money_list = []
for i in range(2 ** n):
    buy_list = []
    money = 0
    for j in range(n):
        if ((i >> j) & 1):

            buy_list.append(understand_list[j])
            money += understand_list[j][0]
    if buy_list == []:
        continue
    buy_list = np.sum(buy_list, axis=0)
    if all([i >= x for i in buy_list]):
        money_list.append(buy_list[0])
if money_list == []:
    print(-1)
else:
    print(min(money_list))

Submission status: Runtime Error

Solution code:
n,m,x=map(int,input().split())
li=[0]*m
for i in range(n):
    c=list(int(input()))
    cl=list(map(int,input().split()))
    nli=li+cl
if min(nli)>=x:
    print(sum(c))
else:
    print("-1")

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
N, M, X = map(int, input().split())
kumi = []
pat = list(range(N))
for _ in range(N):
    kumi.append(list(map(int, input().split())))
ans0 = 10 ** 5 * 12 + 1
ans = 10 ** 5 * 12 + 1
#print(kumi)
test = []
for i in range(N):
    for i2 in itertools.combinations(kumi,i+1):
        arr_i2 = np.array(i2)
        arr_i2_sum = arr_i2.sum(axis = 0)
        if np.all(arr_i2_sum[1:] >= X):
            if ans > arr_i2_sum[0]:
                ans = arr_i2_sum[0]
if ans == ans0:
    print(-1)
else:
    print(ans)import numpy as np
import itertools
N, M, X = map(int, input().split())
kumi = []
pat = list(range(N))
for _ in range(N):
    kumi.append(list(map(int, input().split())))
ans0 = 10 ** 5 * 12 + 1
ans = 10 ** 5 * 12 + 1
#print(kumi)
test = []
for i in range(N):
    for i2 in itertools.combinations(kumi,i+1):
        arr_i2 = np.array(i2)
        arr_i2_sum = arr_i2.sum(axis = 0)
        if np.all(arr_i2_sum[1:] >= X):
            if ans > arr_i2_sum[0]:
                ans = arr_i2_sum[0]
if ans == ans0:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools
N, M, X = map(int, input().split())
kumi = []
pat = list(range(N))
for _ in range(N):
    kumi.append(list(map(int, input().split())))
ans0 = 10 ** 5 * 12
ans = 10 ** 5 * 12
#print(kumi)
test = []
for i in range(N):
    for i2 in itertools.combinations(kumi,i+1):
        arr_i2 = np.array(i2)
        arr_i2_sum = arr_i2.sum(axis = 0)
        #print(arr_i2_sum[1:] >= X)
        if np.all(arr_i2_sum[1:] >= X):
            if ans > arr_i2_sum[0]:
                ans = arr_i2_sum[0]
if ans == ans0:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
from io import StringIO
import unittest

sys.setrecursionlimit(10**5)
def search(n, step, rec, seq, k):
	if rec[n] != -1:
		c = step - rec[n]
		sim = (k - rec[n]) % c
		v = n
		for i in range(sim):
			v = seq[v-1]
		print(v)
		return
	rec[n] = step
	search(seq[n-1], step + 1, rec, seq, k)

def resolve():
	n, k = map(int, input().split())
	seq = list(map(int, input().split()))
	rec = [-1]*(n+1)
	search(1, 0, rec, seq, k)
resolve()

Submission status: Runtime Error

Solution code:
import sys
for i in range(1<<N):	#Bit All Search
	l=[0]*(M+1)
	for j in range(N):
		if((i>>j)&1)==1:
			l=[l[k]+A[j][k] for k in range(M+1)]
	for k in range(M):
		if l[k+1]<X:
			break
	else:
		cost.append(l[0])
cost.sort()
print(-1 if cost==[] else cost[0])

Submission status: Runtime Error

Solution code:
import sys
n,m,x=map(int,input().split())
ac=[[0]*(m+1) for i in range(n)]
a=[[0]*m for i in range(0,n)]
c=[0 for i in range(n)]
for i in range(n):
  ac[i]=list(map(int,input().split()))
  c[i]=ac[i][0]
  a[i]=ac[i][1:m+1]#sliceは上限+１を:の右に代入
cheap=[]
ccc=[]
finished=[]
candi=[]
neighbor=[[] for i in range(2**(n+1)-1)]
neighbor[0]=[1,2]
for i in range(2**(n+1)-1):
  if i<=2**n-2 and i>0:
    neighbor[i].append(2*i+1)
    neighbor[i].append(2*i+2)
    if i%2==0:
      neighbor[i].append((i-2)//2)
    else:
      neighbor[i].append((i-1)//2)
  if i>2**n-2:
    if i%2==0:
      neighbor[i].append((i-2)//2)
    else:
      neighbor[i].append((i-1)//2)
#print(neighbor)     
#ある一つの参考書をを買うことを一つのノード、買わないことを一つのノードで表す。
#このネットワークでは木の深さが参考書番号に対応する。
#深さの浅いものを小さく、同じ深さのものを左から小さい順にノード番号を振る
#i->ノード番号(not 参考書番号)
def dfs(i):
  #print(i)
  check=i in finished
  kaukadouka=[]
  cost=0
  rikaido=[0 for i in range(m)]
  if check==0:
    finished.append(i)
    for j in range(len(neighbor[i])):
      y=neighbor[i][j] in finished
      z=neighbor[i][j] in candi
      if y==0 and z==0:
        candi.append(neighbor[i][j])
    if i>2**n-2:
      o=i
      t=n-1
      while o>0:
        kaukadouka.append(o%2)
        p=min(neighbor[o])
        cost+=c[t]*(o%2)
        for h in range(m):
          rikaido[h]+=a[t][h]*(o%2)
        o=p
        t-=1
      if min(rikaido)>=x:
        cheap.append(cost)
      ccc.append(i)
    if len(candi)>0:
      r=candi.pop()
      dfs(r)
  else:
    r=candi.pop()
    dfs(r)
dfs(0)
#print(cheap)
#print(ccc)
if len(cheap)>0:
  print(min(cheap))
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    n, m, x = nm()
    arr = []
    for _ in range(n):
        temp = nl()
        arr.append(temp)

    costs = []
    for i in range(2**n):
        binary = bin(i)[2:]
        binary = '0'*(m-len(binary)) + binary
        count = [0]*m
        cost = 0
        for i, num in enumerate(binary):
            if num == '1':
                for j in range(m):
                    count[j] += arr[i][j+1]
                cost += arr[i][0]
        #print(binary, cost)
        flag = True
        for value in count:
            if value < x:
                flag = False
        if flag:
            costs.append(cost)
    if costs == []:
        print(-1)
    else:
        print(min(costs))
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

def main():
    n, m, x = nm()
    arr = []
    for _ in range(n):
        temp = nl()
        arr.append(temp)

    costs = []
    for i in range(2**n):
        binary = bin(i)[2:]
        binary = '0'*(m-len(binary)) + binary
        count = [0]*m
        cost = 0
        for i, num in enumerate(binary):
            if num == '1':
                for j in range(m):
                    count[j] += arr[i][j+1]
                cost += arr[i][0]
        #print(binary, cost)
        flag = True
        for value in count:
            if value < x:
                flag = False
        if flag:
            costs.append(cost)
    try:
        print(min(costs))
    except ValueError:
        print(-1)
    

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

ans = float('inf')
for i in range(2**N):
    Level = [0]* M
    Cost = 0
    
    for j in range(N):
        if (i>>j)&1:
            Cost += C[j]
            for k in range(M):
                Level[​ Cost)

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

Submission status: Runtime Error

Solution code:
import itertools

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

for x in itertools.product([0,1], repeat=2):
  cost = 0
  level = [] * M
  judge = True
  ans = 1234567
  for i in range(N):
    if a[i] == 1:
      cost += a[i][0]
      level = [y + z for (y, z) in zip(level, a[i][1:])]
  for j in range(M):
    if any(level[k] < x for k in range(M)):
      judge = False
  if judge:
    ans = min(ans, cost)

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

Submission status: Runtime Error

Solution code:
def check(pair,m,x):
  sum = 0
  
  for i in range(1,m):
    p = 0
    for e in pair:
      p += e[i]
    
    if(p < x):
      return -1
    
  for e in pair:
    sum += e[0]
  return sum
      
n,m,x = (int(x) for x in input().split())
a = []
for i in range(n):
  a.append(tuple([int(x) for x in input().split()]))
  
list = [] 
  
for i in range(2 ** n):
  pair = []
  for j in range(n):
    if((i >> j) & 1):
      pair.append(a[j])
      
  sum = check(pair,m,x)
  if(sum != -1):
    list.append(sum)
print(min(list))

Submission status: Runtime Error

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

# bit = [0 for _ in range(n)]
mincost = 0
cost = 0
learn = [0 for _ in range(n)]
for i in range(n):
	mincost += ca[i][0]

for cnt in range(2**n):
	cost = 0
	learn = [0 for _ in range(n)]

	# bit膳探索
	for i in range(n):
		# bit[i] = (cnt//2**i)%2
		if (cnt//2**i)%2 == 1:
			cost += ca[i][0]
			for j in range(m):
				learn[j] += ca[i][1+j]
	# print(bit)

	# 理解度達成しているか判定
	tassei = True
	for j in range(m):
		if learn[j] < x: tassei = False

	# 達成している and 最小コスト更新している
	if tassei and cost <= mincost:
		mincost = cost
		anytassei = True

if anytassei: print(mincost)
else: print(-1)

Submission status: Runtime Error

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

# bit = [0 for _ in range(n)]
mincost = 0
cost = 0
learn = [0 for _ in range(n)]
for i in range(n):
	mincost += ca[i][0]

for cnt in range(2**n):
	cost = 0
	learn = [0 for _ in range(n)]

	for i in range(n):
		# bit[i] = (cnt//2**i)%2
		if (cnt//2**i)%2 == 1:
			cost += ca[i][0]
			for j in range(m):
				learn[j] += ca[i][1+j]
	# print(bit)

	tassei = True
	for j in range(m):
		if learn[j] < x: tassei = False
	if tassei and cost <= mincost:
		mincost = cost
		anytassei = True

if anytassei: print(mincost)
else: print(-1)

Submission status: Runtime Error

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

# bit = [0 for _ in range(n)]
mincost = 0
for i in range(n):
	mincost += ca[i][0]

for cnt in range(2**n):
	cost = 0
	learn = [0 for _ in range(n)]

	for i in range(n):
		# bit[i] = (cnt//2**i)%2
		if (cnt//2**i)%2 == 1:
			cost += ca[i][0]
			for j in range(m):
				learn[j] += ca[i][1+j]
	# print(bit)

	tassei = True
	for j in range(m):
		if learn[j] < x: tassei = False
	if tassei and cost <= mincost:
		mincost = cost
		anytassei = True

if anytassei: print(mincost)
else: print(-1)

Submission status: Runtime Error

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

INF = 10 ** 9
ans = INF

for bit in range(0, 1 << n):
    cost = 0
    flag = True
    tmp = [0] * m
    for i in range(n):
        if bit & 1 << i:
            cost += C[i]
            for j in range(m):
                tmp[j] += A[i][j]
    for i in range(n):
        if tmp[i] < x:
            flag = False
    if flag:
        ans = min(ans, cost)

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

Submission status: Runtime Error

Solution code:
n,m,x = map(int,input().split())
C = [0]*n
A = [[0]*m for i in range(n)]
for i in range(n):
    b = list(map(int,input().split()))
    C[i] = b[0]
    for j in range(1,m+1):
        A[i][j-1] = b[j]
    
MAX = 100000000000
def dfs(a,c,i):
    if min(a)>=x:
        return cost
    elif i == n:
        return MAX
    total_A = [u+v for (u,v) in zip(a,A[i])]
    return min(dfs(a,c,i+1), dfs(total_A,c + C[i], i+1))

ans = dfs([0]*m,0,0)
if ans == MAX:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
    n,m,r = map(int, input().split())
    dn = [[0] * m for _ in range(n)]
    
    for i in range(n):
        dn[i][:] = map(int, input().split())

    dn = np.array(dn)
    cost = []
    sh = 0
    inf = 10e8
    cost = inf
    k = np.zeros(m+1)
    
    def secom(j,k,cost):
        if j == n:
            
            if np.all(k>=r):
                print(k)
                cost = min(cost,k[0])
                return cost
            else:
                return cost
        
        cost1 = secom(j+1,k,cost)
        k += dn[j]
        cost2 = secom(j+1,k,cost)
        k -= dn[j]
        
        return min(cost1,cost2)
    
    
    cost = secom(0,k,cost)
    if cost == inf:
        print(-1)
    else:
        print(int(cost))
        
        

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

c = []
a = []
for i in range(len(ca)):
    c.append(ca[i][0])
    a.append(ca[i])
    del a[i][0]

ans = 12345678
for i in range(2 ** n):
    cost = 0
    level = [0] * m
    for j in range(n):
        if(i>>j&1):
            cost += c[j]
            for k in range(m):
                level[k] += a[j][k]
    flag = True
    for k in range(m):
        if(level[k] < x):
            flag = False
    if(flag):
        ans = min(ans,cost)
if(ans == 12345678):
    print(-1)
else:
    print(ans)