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:
n,m,x = map(int, input().split())
import numpy as np
b = []
c = []
for i in range(n):
  tmp = list(map(int, input().split()))
  b.append(tmp)
skill = np.array([0 for i in range(m)])
b = np.array(b)
ind = 0
rms = []
cos = 0
ma = float('inf')

for i in range(2**n):
  bins = bin(i)[2:]
  if len(bins) < m:
    bins += "0"*int(m-len(bins))
  bins = np.array(list(map(int,bins)))
  res = (b.transpose() * bins).transpose().sum(axis=0)
  if all(res[1:] > x) and res[0] < ma:
    ma = res[0]
print(ma)

Submission status: Runtime Error

Solution code:
import numpy as np
a,b,c=map(int,input().split())

li=[list(map(int,input().split())) for n in range(a)]
s1=sum([r[1]for r in li])
s2=sum([r[2]for r in li])
s3=sum([r[3]for r in li])
#s1=sum(li[1])
#s2=sum(li[2])

if s3<c or s2<c or s1<c:
    print(-1)
else:
    l1=sorted(li, reverse=True,key=lambda x: x[1])
    sum1=0
    a1=[]
    i=0

    for n in l1:
        sum1+=n[1]
        i+=1
        if c<=sum1:
            a1=l1[:i]
    l2=sorted(li, reverse=True,key=lambda x: x[2])
    sum1=0
    a2=[]
    i=0

    for n in l1:
        sum1+=n[2]
        i+=1
        if c<=sum1:
            a2=l2[:i]
    l3=sorted(li, reverse=True,key=lambda x: x[3])
    sum1=0
    a3=[]
    i=0

    for n in l1:
        sum1+=n[3]
        i+=1
        if c<=sum1:
            a3=l3[:i]
    a1.extend(a2)
    a1.extend(a3)
    a1=list(set(a1))
    print(um([r[0]for r in li]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, M, X = map(int, input().split())
a = 1
if a == 1:
    CA = list(map(int, input().split()))
    if N > 1:
        for i in range(N - 1):
            d = list(map(int, input().split()))
            CA = np.vstack((CA,d))
    C = CA[:,0]
    A = CA[:,1:]

    C_set = []
    for i in range(2 ** (N)):
        book = format(i, '0'+str(N)+'b')
        S = [0] * M
        CC = 0
        for j in range(N):
            if book[j] == "1":
                S = S + A[j,:]
                CC += C[j]
        if min(S) >= X:
            C_set.append(CC)
    if len(C_set) == 0:
        print(-1)
    else:
        print(min(C_set))

Submission status: Runtime Error

Solution code:
n, m, x = map(int, input().split())
p = [[]*n]*(m+1)
for N in range(n):
  p[N] = list(map(int, input().split()))
minimum = 10000000
rikaidos = []*m
for i in range(2**n):
  rikaidos = [0]*m
  for j in range(m):
    rikai = 0
    for k in range(n):
      if ((i >> k) & 1):
        rikai += p[k][j+1]
    if rikai >= x:
      rikaidos[j] = 1
  if m == sum(rikaidos):
    cost = 0
    for k in range(n):
      if ((i >> k) & 1):
        cost += p[k][0]
    minimum = min(minimum, cost)
if minimum == 10000000:
  print(-1)
else:
  print(minimum)

Submission status: Runtime Error

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

cost = 100000000000000000000000
l = list(range(1,N+1))
import itertools
for i in range(1,N+1):
    check_l = list(itertools.combinations(l,i))
    for a in check_l:
        sub_list = [0] * (M + 1)
        for j in range(i):
            for k in range(M+1):
                sub_list[k] += C[a[i]-1][k]
        flag = True
        for p in range(M):
            if sub_list[p+1] < X:
                flag = False
        if flag == True:
            if cost > sub_list[0]:
                cost = sub_list[0]

if cost == 100000000000000000000000:
    print(-1)
else:
    print(cost)

Submission status: Runtime Error

Solution code:
import numpy as np
from itertools import combinations_with_replacement

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

OK = True
CA = np.array(CA)
sums = np.sum(CA,axis=0)
for i in range(1,M):
  if sums[i] < X:
    OK = False
    break
    
As = []
for A in combinations_with_replacement(range(0, N), r=M):
  As.append(set(A))

    
if OK == False:
  print(-1)
else:
  min_ = sums[0]
  for i in As:
    mini_CA = []
    for j in i:
      mini_CA.append(CA[j])
    mini_CA = np.array(mini_CA)
    OK2 = True
    sums = np.sum(mini_CA,axis=0)
    for k in range(1,M):
      if sums[k] < X:
        OK2 = False
        break
    if OK2 == True and sums[0] < min_:
      min_ = sums[0]
      
print(min_)

Submission status: Runtime Error

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

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


for i in range(1, N+1):
    for pair in itertools.combinations(values_list, i):
        this_m_dict = {}
        this_cost = 0
        for item in pair:
            for j in range(1, M+1):
                this_m_dict[j] = this_m_dict.get(j, 0) + item[j]
            this_cost += item[0]
        for myvalue in this_m_dict.values():
            if myvalue < X:
                break
        ans = min(this_cost, ans)

print(ans)

Submission status: Runtime Error

Solution code:
#167
#c
import sys
import itertools
import numpy
n,m,x  = map(int, input().split())
zentan = itertools.product([0,1],repeat = m)
condi  = []
for i in range(n):
    ln = list(map(int, input().split()))
    condi.append(ln)
cost_min = 10**10
for i in zentan:
    cost = 0
    skills= [0]*m
    
    for k,j in enumerate(i): # zentan i 
      cost += condi[k][0]*j
      for c in range(1,m +1):
        skills[c-1]+= condi[k][c]*j
    
    if min(skills) >= x:
        cost_min = min(cost,cost_min)

if cost_min<10**10:
    print(cost_min)
else:
    print('-1')

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

#入力
input_line = input()
input_line = input_line.split(" ")
N = int(input_line[0])
M = int(input_line[1])
X = int(input_line[2])

#値段
C = []

#学習値
A = [[0 for j in range(M)] for i in range(N)]


#値段の合計値C_sum
C_sum = 0

#学習の合計値
A_sum = [0 for i in range (M)]

#変数t
t = 0

#変数
l = 0

for i in range (N):
    input_line = input()
    input_line = input_line.split(" ")
    C.append(int(input_line[0]))
    for j in range (M):
        A[i][j] = int(input_line[j+1])

#全ての参考書を購入
for i in range(N):
    C_sum += C[i]
    for j in range(M):
        A_sum[i] += A[j][i]

for i in range (N):
    if A_sum[i] > X:
        t+=1

if t != M:
    print("-1")
else:
    for i in range(N):
        l = C_sum
        C_sum = C_sum - C[i]
        for j in range(M):
            t = A_sum[i]
            A_sum[i] = A_sum[i] - A[j][i] 
            if A_sum[i] < X:
                A_sum[i] = t
                C_sum = l 
                break
            else:
                continue
            break

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

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

clist=[]
clist2=[]
for i in range(n):
    clist = list(map(int, input().split()))
    clist2.append(clist)

test_list = []

for i in range(1, n+1):
    test_list.append(list(itertools.combinations(clist2, i)))

test_list = sum(test_list, [])

def hantei(hant):
    test2 = np.sum(hant, axis=0)
    if all([True if (i >= x) else False for i in test2[1:m+1]]):
        return test2[0]
    else:
        return -1

test3 = list(map(hantei, test_list))

if max(test3) == -1:
    print(-1)
else:
    print(sorted(set(test3))[1])

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
N,M,X=map(int,input().split())
lista=[]
for i in range(N):
    lista.append(list(map(int,input().split())))
lista=np.array(lista)
cost=1000000000000000
judge=[X]*M
data=[k for k in range(1,N+1)]
for i in range(1,N+1):
    a=list(itertools.combinations(data,i))
    for j in a:
        clist=np.array([0]*(M+1))
        for k in j:
            clist=clist+lista[k-1]
        if all(clist[1:]>=judge):
            if clist[0]<cost:
                cost=clist[0]
                m=j
c=0
for i in m:
    c+=lista[i][0]

print(c)

Submission status: Runtime Error

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

for  i in range(M):
  if sum(A[:,i]) < X:
    print(-1)
    exit()
    
v = list(range(N))
SCORE=[0]*N
MONEY=0
for i in range(N+1):
  com = list(itertools.combinations(v,i));
  for j in com:
    for k in j:
      MONEY = MONEY + com[j][k]
      SCORE = SCORE + A[:,k]
      if all(x >= X for x in SCORE):
        print(MONEY)

Submission status: Runtime Error

Solution code:
import itertools
N,M,X = map(int,input().split())
A = [0,0,0,0]
C = []
Z = []
cz = []
for i in range(N) :
    C.append(list(map(int,input().split())))

for i in range(2,N+1) :
    c = list(itertools.combinations(C,i))
    for j in range(len(c)) :
        A = [0,0,0,0]
        cj = c[j]
        for k in range(i) :
            ck = cj[k]
            A[0]+= ck[0]
            A[1] += ck[1]
            A[2] += ck[2]
            A[3] += ck[3]
        Z.append(A)

for i in range(len(Z)) :
    zi = Z[i]
    if zi[1]>=X and zi[2]>=X and zi[3]>=X :
        cz.append(zi[0])        

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

Submission status: Runtime Error

Solution code:
def remove(B, ran, sm):
    ans = sm
    for r in ran:
        flag = 1
        for a in A[1:]:
            if l - r < x:
                flag = 0
                break
        if flag:
            new = [rr for rr in ran if rr != r]
            cand = remove([b - a for b, a in zip(B[1:], A[1:])], new, sm - a[0])
            if ans > cand:
                ans = cand
    return ans
def main():
    n, m, x = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(n)]
    L = [sum(a[i] for a in A) for i in range(m+1)]
    print(L)
    if any (l < x for l in L):
        print(-1)
        return
    remove(B, range(1, n), L[0])
main()

Submission status: Runtime Error

Solution code:
import numpy as np  # NumPyモジュールをインポートする
import itertools

val = input()
val = val.split(" ")
val = [int(i) for i in val]  # 全部intに変換

I = np.zeros((val[0], val[1]+1))

for i in range(val[0]):
    val2 = input()
    val2 = val2.split(" ")
    val2 = [int(i) for i in val2]  # 全部intに変換
    I[i] = val2

seq = [i for i in range(val[0])]  # 組み合わせを考える
print(seq)

for i in range(val[0]):
    Comb = list(itertools.combinations(seq, i+1))
    # print(Comb)
    for j in Comb:
        Com_list = list(j)
        # print(Com_list)
        I_sum = [[I[k][l+1] for k in Com_list] for l in range(val[1])]
        print(I_sum)
        ans = [sum(i) for m in I_sum]
        print('ans=', ans)
        # if (ans >= 10):
        #     print(I[Com_list])

Submission status: Runtime Error

Solution code:
from itertools import *
n,m,x=[int(i) for i in input().split()]
l=[[int(i) for i in input().split()] for j in range(n)]
c=[i[0] for i in l]
l=[i[1:] for i in l]
p=list(product([0,1],repeat=m))
s=[[sum([l[k][j]*i[j] for k in range(n)]) for j in range(m)] for i in p]
print(s)
s=[c[i] for i in range(n) if all([s[i][j]>=x for j in range(m)])]
print(s)

Submission status: Runtime Error

Solution code:
N,M,X= map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
K=np.array([0*M])
m=[]

import numpy as np


def dfs(i, sum,K):
    # n 個決め終わったら、今までの和 sum が k と等しいかを返す
    if i == N:
        count=0
        for j in K:
           if j>=X:
                count+=1
        if count==M
            m.append(sum)
        return count==M
            

    # a[i] を使わない場合
    if dfs(i + 1, sum+K[i][0],K+np.array([for j in A[i][1:]]):
        return True

    # a[i] を使う場合
    if dfs(i + 1, sum,K):
        return True

    # a[i] を使う使わないに拘らず k が作れないので False を返す
    return False
print(min(m) if dfs(0,0,K) else -1)

Submission status: Runtime Error

Solution code:
#N, M, X = [int(n) for n in input().split()]

#CA = [list(map(int, input().split())) for n in range(N)]

#print(N,M,X)
#print(CA)

min_cost = 12*10**5


def dfs(CA, cost, skills, cur, used, min_cost):
  #Pdb().set_trace()
  #print(cur)
  skills = [skills[i] + n for i, n in enumerate(CA[cur][1:])]
  used += [cur]
  cost += CA[cur][0]
  
  if all([s >= X for s in skills]):
  	return cost
  else:
    candidates = [n for n in range(N) if n not in used]
    prev_used = used
    prev_skills = skills
    prev_cost = cost
    for i in candidates:
        min_cost = min(min_cost, dfs(CA, prev_cost, prev_skills, i, prev_used, min_cost))
  return min_cost
       

for i in range(N):
  Pdb().set_trace()
  used = []
  cost = 0
  skills = [0] * M
  min_cost = min(min_cost, dfs(CA, cost, skills, i, used, min_cost)) 

print(min_cost)

Submission status: Runtime Error

Solution code:
book_list,method,max_proficiency=map(int,input().split())
line = [[0 for i in range(method+1)] for j in range(book_list)]
h=100000
s=0
check=0
cont=0
for i in range(book_list):
    line[i] =list(map(int, input().strip().split()))
rate_list=[0 for i in range(book_list)]
for i in range (book_list):
    rate_list[i]=line[i][0]/line[i][1]
ex_list=rate_list
ex_list.sort()
rank_list=[0 for i in range(book_list)]
for i in range(book_list):
    for j in range(book_list):
        if rate_list[i]==ex_list[j]:
            rank_list[j]=i
for i in range(1,book_list):
    for j in range (1,method+1):
        for m in rank_list:
            s=s+1
            check=check+line[m][j]
            if s==i:
                break
        if check<max_proficiency:
            break
        else:
            cont=cont+1
        s=0
        check=0
    if i==book_list-1 and cont==book_list:
        i=i+1
    last=i
    if cont==book_list:
        break
    cont=0
if last<book_list-1 or last==book_list :
    for i in rank_list:
        yuan=yuan+line[i][0]
    print(yuan)
else:
    print(-1)

Submission status: Runtime Error

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

yen = []
scores = []
def dfs(m,i,score_sum,y):
  if i == N:
    scores.append(score_sum)
    yen.append(y)
    return
  dfs(m,i+1,score_sum,y)
  dfs(m,i+1,score_sum+l[i][m],y+l[i][0])

for k in range(1,M+1):
  dfs(k,0,0,0)

cycle = len(scores)// M

goodyen = []
for k in range(len(yen)):
  cnt = 0
  for m in range(M):
    if scores[ m * cycle + k] >= X:
      cnt += 1
  if cnt == M:
    goodyen.append(yen[k])
print(min(goodyen))

Submission status: Runtime Error

Solution code:
import sys
N,M,X = map(int,input().split())
book_list = list()
for i in range(N):
    book_list.append(list(map(int,input().split())))

for i in range(N):
    book_list[i].append(book_list[i][0]/sum(book_list[i][1:M]))
book_list.sort(key=lambda x: x[-1])

dp = [-1 * X]*M

cost = 0
for book in book_list:
    dp_dash = list(map(sum, zip(dp, book[1:M+1])))
    if sum(dp_dash) > sum(dp):
        dp = dp_dash
        cost += book[0]
    if sum(dp) > 0:
        break
    # print(dp_dash)

for i in dp:
    if i < 0 :
        print(-1)
        sys.exit()
print(cost)

Submission status: Runtime Error

Solution code:
import itertools
import sys

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

s = [i for i in range(m)]
t = []
list_num = []

for i in range(m):
  t.append(list(map(list, itertools.combinations(s, i + 1))))

for i in t:
  for j in i:
    k = [0] * (m + 1)
    for z in j:
      k = tuple(x + y for (x,y) in zip(k, num[z]))
    list_num.append(k)


list_num = list(sorted(list_num, key =lambda w : w[0]))
q = []

flag2 = 0

for i in list_num:
  flag = 1
  for j in range(1, m + 1):
    if(i[j] < x):
      flag = 0
  if(flag == 1):
    q.append(i[0])
    flag2 = 1

if(flag2 == 1):
  print(min(q))
else: 
  print(-1)

Submission status: Runtime Error

Solution code:
import numpy as np

global N, M, X, A, C

def check(l, m_l):
    global M, X, A, C
    sum_ = np.zeros(M)
    for i in range(1, len(l)-1):
        sum_ += A[l[i]-1]
    flag = True
    for i in range(M):
        if(sum_[i] < X):
            flag = False
            break
    if(flag == True):
        money = 0
        for i in range(1, len(l)-1):
            money += C[l[i]-1]
        m_l.append(money)

def dfs(l, m_l):
    global N, M, X, A, C
    check(l, m_l)
    tail = l[len(l)-1]
    for i in range(tail+1, N+1):
        l.append(i)
        dfs(l, m_l)
        l.pop()

def main():
    global N, M, X, A, C, money_l
    args = input().rstrip().split(' ')
    N, M, X = int(args[0]), int(args[1]), int(args[2])
    A = np.zeros((N, M))
    C = np.zeros(N)
    for i in range(N):
        args = input().rstrip().split(' ')
        C[i] = int(args[0])
        for j in range(1, 1+M):
            A[i][j-1] = int(args[j])
    money_l = []
    dfs([0], money_l)
    
    print(int(min(money_l)))
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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



def check(xxx):
    tmp = 0
    for i in range(1,m):
        if x > xxx[i]:
            tmp = 1
    if tmp == 0:
        return True
    else:
        return False

def tashi(g,h):
    shoki = [0] * (m + 1)
    for i in range(m+1):
        shoki[i] = g[i] + h[i]
    return shoki
        

def aaa(asum,b):
    if check(asum):
        ans = min(ans, asum[0]) 
        return True
    if b == n:
        return False
    if aaa(asum, b+1):
        return check(asum)
    if aaa(tashi(asum,c[b]),b+1):
        return check(asum)


if aaa(shoki, 0):
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import itertools

N,M,X = map(int,input().split())
str_list = []
for i in range(N):
    str_list.append(list(map(int,input().split())))
#print(str_list)


n = len(str_list)

b_pairs = []
for j in range(0, n+1):
    b_pairs += list(itertools.combinations(str_list, j))
    # 単に b_pairs += itertools.combinations(b, i) でも可

#print(len(b_pairs))
numl = []
for k in b_pairs:
  #print(k)
  num = 0
  ml = [0]*(M-1)
  for l in k:
    for d in range(1,M):
      ml[d-1] += l[d]
    num+=l[0]
  #print(ml)
  if min(ml) >= X:
    numl.append(num)
if len(numl) == 0:
  print(-1)
else:
  print(min(numl))

Submission status: Runtime Error

Solution code:
N, M, X = map(int,input().split())
num_list = [list(map(int, input().split())) for _ in range(n)]
list = [0]*M
price = 0
for i in range(N):
    price += [i][0]
    for j in range(M):
    list[j] = num_list[i][j]
if sum(list) >= 10*M:
    print(price)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
def resolve():

    n, m,x = map(int, input().split())
    c=[]
    a=[]
    ans=10**13
    nedan=0
    rikai=[0]*m
    for i in range(n):
        A = list(map(int, input().split()))
        c.append(A[0])
        a.append(A[1:])
        for j in range(m):
            rikai[j]+=a[i][j]
    if min(rikai)>=x:
        for Bin in range(2**n):
            N = [str(x) for x in list(str(bin(Bin+2**13)))]
            N.pop(0)
            N.pop(0)
            for hon in range(n):
                if N[hon + 1] == 1:
                    for aru in range(m):
                        rikai[aru]+=a[hon][aru]
                    nedan+=c[hon]
            if min(rikai)>=x:
                ans=min(ans,nedan)
            rikai=[]
            nedan=0
        print(ans)

    else:
        print(-1)
resolve()

Submission status: Runtime Error

Solution code:
n,k,x = (int(x) for x in input().split())
C = []
A = []
for i in range(n):
    list = [int(i) for i in input().split()]
    C.append(list[0])
    A.append(list[1:])
i = 0
case = [0]*(2**n)
chk = []
for i in range(2**n):
    chk.append([0]*m)
i = 0
for i in range(2 ** n):
    for j in range(n):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            case[i] += C[j]
            for l in range(m):
                chk[i][l] += A[j][l]
i = 0
j = 0
ans = []
flag = [True]*(2**n)
for i in range(2**n):
    for j in range(m):
        if chk[i][j]<x:
            flag[i] = False
    if flag[i]:
        ans.append(case[i])

if ans==[]:
    print(-1)
else:
    print(min(ans))

Submission status: Runtime Error

Solution code:
n, m, x = list(map(int,input().split()))
c = []
a = []
for i in range(n):
  a0 = list(map(int,input().split()))
  c.append(a0[0])
  a.append(a0[1:m])
  
comp = [[0] * m for i in range(2 ** n)]
price = [0] * (2 ** n)
k = 0
 
def calculation(i):
  global comp
  global price
  global k
  for j in range(m):
    comp[k, j] = a[i, j]
  price[k] += c[i]
  k += 1
  calculation(i + 1)
  k += 1
  calculation(i + 1)
  
calculation(0)
answer = max(price)
for i in range(2 ** n):
  if min(comp[i, *]) >= x:
    answer = min(answer, price[i])
print(answer)

Submission status: Runtime Error

Solution code:
n,m,x=map(int,input().split())
from itertools import combinations
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
l1=[]
for i in range(m):
    l1.append(i)
l2=[]
for i in range(1,m+1):
    lx=[0]*i
    a=0
    for lx in combinations(l1,i):
        ly=[0]*m
        for p in range(1,m+1):
            for k in lx:
                ly[p-1]+=l[k][p]
        for k in lx:
            a+=l[k][0]
        for j in ly:
            if j<x:
                a=0
                break
        if a!=0:
            l2.append(a)
print(min(l2))

Submission status: Runtime Error

Solution code:
N,M,X= map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
K=np.array([0*M])
m=[]

import numpy as np


def dfs(i, sum,K):
    # n 個決め終わったら、今までの和 sum が k と等しいかを返す
    if i == N:
        count=0
        for j in K:
            
            while j>=X:
                count+=1
        if count==M
            m.append(sum)
        return count==M
            

    # a[i] を使わない場合
    if dfs(i + 1, sum+K[i][0],K+np.array([for j in A[i][1:]]):
        return True

    # a[i] を使う場合
    if dfs(i + 1, sum,K):
        return True

    # a[i] を使う使わないに拘らず k が作れないので False を返す
    return False
print(min(m) if dfs(0,0,K) else -1)

Submission status: Runtime Error

Solution code:
N, M, X = list(map(int, input().split()))
weight = []
value = []
for _ in range(N):
    n = list(map(int, input().split()))
    value.append(n.pop(0))
    weight.append(n)
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp = [[-inf for i in range(W+1)] for j in range(N+1)]
  #print(dp)
  for i in range(W+1): dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(W+1):
        #print(i,w)
        if min(weight[i])>=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
            dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
        else: #入る可能性はない
            dp[i+1][w]=dp[i][w]
  return dp[N][W]

l =  knapsack(N,X,weight,value)

print(l)

Submission status: Runtime Error

Solution code:
N, M, X = map(int, input().split())
C = [0]*N

import itertools
import numpy as np      
a = 0

for i in range(N):
  C[i] = list(map(int, input().split()))

k = 1
  
while k <= M:
  goukei = 0
  for j in range(N):
    goukei += C[j][k]
  if goukei < X:
    a = 1
  k += 1
  
if a == 1:
  print("-1")
  
else:
  l = 1
  for n in range(1,N+1):
    Y = [0]*(M+1)
    for X in itertools.combinations(C,n):

Submission status: Runtime Error

Solution code:
N,M,X=map(int,input().split())
li=[]
Ans=100001

for i in range(N):
    array=list(map(int,input().split()))
    li.append(array)

for j in range(2**N):
    b=bin(j)
    b=b[2:]
    b="0"*(N-len(b))+b
    
    
    c=0
    x=0
    y=0
    z=0

    for k in range(len(b)):
        if b[k]==str(1):
            c+=li[k][0]
            x+=li[k][1]
            y+=li[k][2]
            z+=li[k][3]
    if x>=X and y>=X and z>=X and Ans>c:
        Ans=c
    else:
        pass

if Ans==100001:
    print("-1")
else:
    print(Ans)

Submission status: Runtime Error

Solution code:
import itertools

n,m,x=map(int,input().split())
c=[list(map(int,input().split())) for i in range(n)]
c=list(itertools.permutations(c))
li=[0]*(n+1)
ans=set()
te=1

for i in range(len(c)):
    li=[0]*(n+1)
    for j in range(n):
        t=c[i][j]
        flug=0
        for k in range(m+1):
            li[k]+=t[k]
            if li[k]<x:
                flug=1
        else:
            if flug==0:
                ans.add(li[0])
                te=0

if te==1:
    print("-1")
else:
    print(min(ans))

Submission status: Runtime Error

Solution code:
import numpy as np

global N, M, X, A, C

def check(l, m_l):
    global M, X, A, C
    sum_ = np.zeros(M)
    for i in range(1, len(l)-1):
        sum_ += A[l[i]-1]
    flag = True
    for i in range(M):
        if(sum_[i] < X):
            flag = False
            break
    if(flag == True):
        money = 0
        for i in range(1, len(l)-1):
            money += C[l[i]-1]
        m_l.append(money)

def dfs(l, m_l):
    global N, M, X, A, C
    check(l, m_l)
    tail = l[len(l)-1]
    for i in range(tail+1, N+1):
        l.append(i)
        dfs(l, m_l)
        l.pop()

def main():
    global N, M, X, A, C, money_l
    args = input().rstrip().split(' ')
    N, M, X = int(args[0]), int(args[1]), int(args[2])
    A = np.zeros((N, M))
    C = np.zeros(N)
    for i in range(N):
        args = input().rstrip().split(' ')
        C[i] = int(args[0])
        for j in range(1, 1+M):
            A[i][j-1] = int(args[j])
    money_l = []
    dfs([0], money_l)
    
    print(min(money_l))
    
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N, M, X = map(int,input().split())
num_list = [list(map(int, input().split())) for _ in range(n)]
list = [0]*M
price = 0
for i in range(N):
    price += [i][0]
    for j in range(M)
    list[j] = num_list[i][j]
if sum(list) >= 10*M:
    print(price)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import copy

z = list(map(int,input().split()))
n = z[0]
m = z[1]
x = z[2]

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

def judge(p):
    for i in range(len(p[0])-1):  #aの要素の個数m
        count = 0
        for j in range(len(p)):  #pの要素の個数n
            count += p[j][i+1]
        if count < x:
            return -1
    return 1

#iはAのi番目をさす。
i = 1
def dec(p,i):
    if i>m:
        cost = 0
        for j in range(len(p)):
            cost += p[j][0]
        print(cost)
    else:
        q = [0]*len(p)
        for k in range(len(p)):
            q[k] = p[k][i]/p[k][0]
        minn = q.index(min(q))
        p1 = copy.deepcopy(p)
        p1.pop(minn)
        if judge(p1)==1:
            p.pop(minn)
            dec(p,i)
        else:
            dec(p,i+1)


if judge(b)!=1:
    print(-1)
else:
    dec(b,1)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M,X=map(int,input().split())
C = [[0 for i in range(M+1)] for j in range(N)]
for i in range(N):
    C[i]=(list(map(int,input().split())))
paymin=float('inf')

def python_list_add(in1, in2):
    wrk = np.array(in1) + np.array(in2)
    return wrk.tolist()

for i in range(2 ** N):#これは品数.i番目の品のオンオフ
    bag=[0*(M+1)]
    total=0
    for j in range(M):
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            for k in range(1,M-1):
                #print("bag,C[k]=",bag,C[k])
                bag=python_list_add(bag, C[k])# フラグが立っていたら 各要素を全部足し合わせ
                #print("newbag",bag)
            if all(i >= X for i in bag[1:]) and bag != [0]:
                print("条件を超えた",bag)
                if paymin > bag[0]:
                    paymin=bag[0]
if paymin==float('inf'):
    print("-1")
else:
    print(paymin)

Submission status: Runtime Error

Solution code:
import itertools

nums = [int(e) for e in input().split()]

list0 = []
A = []
A0 = list(range(0,nums[0]))
for i in range(0, nums[0]):
    val = [int(e) for e in input().split()]
    list0.append(val)
    for x in itertools.combinations(A0,i+1):
        A.append(list(x))

X = []
for i in range(0,len(A)):
    Y = [0] * (nums[1]+1)
    for j in range(0,len(A[i])):
        Y = [x + y for (x, y) in zip(Y,list0[A[i][j]])]
    if Y[1] >= nums[2] and Y[2] >= nums[2] and Y[3] >= nums[2]:
        X.append(Y[0])

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

Submission status: Runtime Error

Solution code:
n, m, x = map(int,input().split(' '))
a = [[] for i in range(n)]
e = [0] * m
sc = [0] * m
for i in range(n):
    l = list(map(int, input().split(' ')))
    l.append(l[0] / sum(l[1:]))
    a[i] = l
a.sort(key = lambda v : v[-1:])
p = 0
for i in a:
    p += i[0]
    for j in range(m):
        e[j] += i[j + 1]
        sc[j] = 1 if e[j] >= x else 0
    if sum(sc) == m:
        break
        
    
r = p if sum(sc) == m else -1
print(r)