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())
xl = [list(map(int, input().split())) for _ in range(n)]

ans = 10**7
for i in range(2 ** n):
    op = ["1"] * n  
    skl=[0]*m
    cost =0
    for j in range(n):
        if ((i >> j) & 1):
            op[n - 1 - j] = "0"
#買う本のパターン作成終了
    for k in range(0,n):
        if op[k]=="1":
            for l in range(1,m+1):
                skl[l-1] = skl[l-1]+xl[k][l]
            cost += xl[k][0]
    if min(skl)>=x:
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
A=[[0]*(m+1) for i in range(n)]
for i in range(n):
  A[i]=list(map(int,input().split()))
ans=10**10
for i in range(2**n):
  s=format(i,"20b")
  S=[]
  for j in range(n):
    if s[-1-j]=="1":
      S.append(j)
  X=[0]*m
  c=0
  for j in range(len(S)):
    c+=A[S[j]][0]
    for k in range(m):
      X[k]+=A[S[j]][k+1]
  f=0
  for j in range(m):
    if X[j]<x:
      f=1
  if f==0:
    if c<ans:
      ans=c
if ans==10**10:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

mx = 9999999999999
for i in range(2 ** n):
    ans = [0] * m
    price = 0
    s = bin(i)[2: ]
    s = '0' * (n - len(s)) + s
    # print(s, ans)
    for j in range(len(s)):
        if s[j] == '1':
            for k in range(m):
                ans[k] += l[j][k]
            price += cost[j]
    # print(s, ans)
    # print()
    ch = 1
    for j in range(m):
        if ans[j] < x:
            ch = 0
            break
    if ch:
        mx = min(mx, price)
if mx == 9999999999999: print(-1)
else: print(mx)

Submission status: Accepted

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

def f(cost,rikai,index):
    if all([x<=i for i in rikai]):
        return cost
    elif n<=index:
        return -1
    v1=f(cost,rikai,index+1)
    v2=f(cost+c[index],[rikai[i] + a[index][i] for i in range(len(rikai))],index+1)
    if v1!=-1 and v2!=-1:
        cost=min(v1,v2)
    elif v1!=-1:
        cost=v1
    elif v2!=-1:
        cost=v2
    else:
        cost=-1
    return cost

print(f(0,[0 for i in range(m)],0))

Submission status: Accepted

Solution code:
import numpy as np
from itertools import combinations

n, m, x = map(int, input().split())
lis = [list(map(int, input().split())) for _ in range(n)]
# print(n, m, x, lis)

ans = 10 ** 9
for i in range(1, n+1):
    combination = combinations(range(n), i)
    for comb in combination:
        init = np.zeros(m+1)
        for ind in list(comb):
            init = init + np.array(lis[ind])
        if np.amin(init[1:]) >= x:
            ans = min(ans, init[0])
if ans < 10**9:
    print(int(ans))
else:
    print(-1)

Submission status: Accepted

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

ans = 10 ** 9

for i in range(2**N):
    tmp = [0] * M
    tmp2 = 0
    for j in range(N):
        if i >> j & 1:
            for k in range(M):
                tmp[k] += A[j][k]
            tmp2 += C[j]
    flag = True
    for l in range(M):
        if tmp[l] < X:
            flag = False
    if flag:
        ans = min(ans, tmp2)
if ans != 10 ** 9:
    print(ans)
else:
    print("-1")

Submission status: Accepted

Solution code:
from itertools import combinations
n, m, x = list(map(int, input().split()))
ca = [list(map(int, input().split())) for _ in range(n)]
mincost = 1e+7
can = False
for i in range(1, n + 1):
    for J in combinations(range(n), i):
        score = [0] * m
        cost = 0
        for j in J:
            cost += ca[j][0]
            for k in range(m):
                score[k] += ca[j][k + 1]
        if all([a >= x for a in score]):
            mincost = min(mincost, cost)
            can = True
if can:
    print(mincost)
else:
    print('-1')

Submission status: Accepted

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

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


ans = 10**18
flag = False
for i in range(2 ** N):
    tmp = 0
    gakusyu = [0]*M
    for j in range(N):
        if ((i >> j) & 1):
            gakusyu = [x+y for x, y in zip(A[j], gakusyu)]
            tmp += C[j]
    if all([True if rikaido >= X else False for rikaido in gakusyu]):
        ans = min(ans, tmp)
        flag = True
if flag:
    print(ans)
else:
    print("-1")

Submission status: Accepted

Solution code:
from __future__ import print_function

from functools import reduce
from operator import mul
from collections import Counter
from collections import deque
from itertools import accumulate
from queue import Queue
from queue import PriorityQueue as pq
from heapq import heapreplace
from heapq import heapify
from heapq import heappushpop
from heapq import heappop
from heapq import heappush
import heapq
import time
import random
import bisect
import itertools
import collections
from fractions import Fraction
import fractions
import string
import math
import operator
import functools
import copy
import array
import re
import sys
sys.setrecursionlimit(500000)


input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


def main():
    n, m, x = map(int, input().strip().split())
    books = []
    for i in range(n):
        c_temp, *A_temp = map(int, input().strip().split())
        books.append((c_temp, A_temp))
    eprint('books ', end=':\n')
    eprint(books)

    #
    ans = sys.maxsize
    for case in range(2 ** n):	 # 場合ループ # nは人とかモノとかの個数
        l_bin = list(map(int, (format(case, 'b').zfill(n))))
        # eprint('l_bin ',end=': ')
        # eprint(l_bin)

        # flag=0
        lvalue = [0 for _ in range(m)]
        cost = 0
        for index_object in range(n):	  # 人とかモノとかループ
            if l_bin[index_object] == 1:				   # その桁がyesだと仮定している場合
                cost += books[index_object][0]
                for j in range(m):
                    lvalue[j] += books[index_object][1][j]
                    
            else:								 # その桁がnoだと仮定している場合
                pass
        #
        suc_flag = 1
        for i in range(m):
            suc_flag *= (lvalue[i] >= x)
        if suc_flag:
            ans = min(ans, cost)
    if ans == sys.maxsize:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x= map(int,input().split())
texts = [list(map(int,input().split())) for i in range(n)]
judge = False
min_ex = 10**7

for bit in range(2**n):
    understand = [0]*m
    expense = 0
    for i in range(n):
        if bit>>i & 1:
            expense += texts[i][0]
            for j in range(m):
                understand[j] += texts[i][j+1]
    if min(understand) >= x:
        judge = True
        min_ex = min(expense, min_ex)

if judge:
    print(min_ex)
else:
    print(-1)

Submission status: Accepted

Solution code:
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy
N, M, X = map(int, input().split())
dump(N, M, X)
C = [0]*N
A = [[]]*N
dump(C, A)
for i in range(N):
    I = list(map(int, input().split()))
    dump(I)
    C[i] = I[0]
    A[i] = I[1:]
ans = -1
for p in it.product([True, False], repeat=N):
    buy = list(p)
    understand = [0]*M
    pay = 0
    for i in range(N):
        if buy[i]:
            pay += C[i]
            for j in range(M):
                understand[j] += A[i][j]
    if all([u >= X for u in understand]):
        ans = pay if ans == -1 else min(ans, pay)

print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

items = np.array([list(map(int, input().split())) for _ in range(N)])

min_v = 10**18
for n in range(1, N+1):
  for c in itertools.combinations(range(N), n):
    tmp = np.sum(items[[c]], axis=0)
    c = tmp[0]
    a = tmp[1:]
    if M == np.count_nonzero(a >= X):
      min_v = min(min_v, c)
if min_v == 10**18:
  print(-1)
else:
  print(min_v)

Submission status: Accepted

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

ans = 1000000000000
flag = 0
for i in range(2**n):
    u = [0]*m
    tmp = 0
    for j in range(n):
        if ((i>>j)&1) :
            l = li[j]
            tmp += l[0]
            for k in range(m):
                u[k] += l[k+1]
    if all(i >= x for i in u):
        flag = 1
        ans = min(tmp, ans)
if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
def check(l):
    pay = 0
    udst=[0]*M
    for i,e in enumerate(l):
        if e == 1:
            pay += Cs[i]
            for m in range(M):
                udst[m] += As[i][m]
    if min(udst) >= X:
        return pay
    else:
        return 10**7

def f(l,minval):
    if len(l) == N:
        return check(l)
    
    for apnd in [0,1]:
        ans = f(l+[apnd],minval)
        if ans < minval:
            minval = ans
    return minval

N,M,X = map(int, input().split())
Cs=[]
As=[]
for _ in range(N):
    _tmp = list(map(int,input().split()))
    Cs.append(_tmp[0])
    As.append(_tmp[1:])

ans = f([],10**7)

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

Submission status: Accepted

Solution code:
def main():
    N,M,X=map(int,input().split())
    arr=[]
    for _ in range(N):
        arr.append(list(map(int,input().split())))
    minn=int(13e9)
    for counter in range(1<<N):
        cost=0
        knowledge=[0]*M
        for i in range(N):
            if counter&(1<<i)!=0:
                cost+=arr[i][0]
                for j in range(1,M+1):
                    knowledge[j-1]+=arr[i][j]
        flag=True
        for j in range(M):
            if knowledge[j]<X:
                flag=False
                break
        if flag:
            minn=min(cost,minn)
    if minn==13000000000:
        print(-1)
    else:
        print(minn)
if __name__=='__main__':
    main()

Submission status: Accepted

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

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

ans = []

for i in range(1, 2 ** n):
    com = [0] * n
    for j in range(n):
        if i >> j & 1 == 1:# iのj番目の桁が1かどうか
            com[j] += 1
    ind = [i for i, x in enumerate(com) if x == 1]
    score = [0]*m
    money = 0
    for j in ind:
        money += c[j][0]
        for l in range(m):
            score[l] += c[j][l+1]
    if all([l >= x for l in score]):
        ans.append(money)

if not ans:
    print("-1")
else:
    print(min(ans))

Submission status: Accepted

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

l = np.array(l)
val = 9999999
for i in range(2 ** n):
  curr = np.array([0 for _ in range(m+1)])
  for j in range(n):
    if ((i >> j) & 1):
      curr += l[j]
  flag = True
  for k in range(m):
    if curr[k+1] < x:
      flag = False
  if flag:
    if val > curr[0]:
      val = curr[0]
      
if val == 9999999:
  print("-1")
else:
  print(val)

Submission status: Accepted

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

dic = {} ;
dic [ tuple ( [ 0 for x in range ( M ) ] ) ] = 0 ;
for c in range ( N ) :
	l1  = list ( map ( int  ,input().strip().split(" ") )  ) ;
	dic2 = {} ; 

	for t in dic :

		if t in dic2 :
			dic2[t] = min ( dic2[t] , dic[t] ) ;
		else :
			dic2[t] = dic[t] ;

		x2 = l1[0] + dic[t] ;
		l2 = list ( t ) ;
		for x in range ( M ) :
			l2[x] += l1[x+1] ;

		t2 = tuple( l2 ) ; 
		if t2 in dic2 :
			dic2[t2] = min ( dic2[t2] , x2 ) ;
		else :
			dic2[t2] = x2 ;
	dic = dic2 ;

L = [] ;
for t in dic :
	if any(map(lambda x :x<X , t ) ) : continue ;
	L.append  ( t ) ;
if len(L) ==0 : 
	print ( -1 ) ; 
else :
	print ( min (  map ( lambda x:dic[x] , L ) ) ) ;

Submission status: Accepted

Solution code:
import numpy as np
ans = 10 ** 7
n, m, x = map(int, input().split())
L = [0] * n
for i in range(n):
    L[i] = list(map(int,input().split()))

for i in range(2 ** n):
    list_0 = [0] * n
    for j in range(n):
        if ((i >> j) & 1):
            list_0[n - 1 - j] = 1
    Li = np.array([0] * m)
    tmp = 0
    for k in range(n):
        if list_0[k] == 1:
            tmp += L[k][0]
            Li += np.array(list(L[k][1:]))
    if (Li >= x).all():
        ans = min(ans, tmp)
print(ans if ans != 10 ** 7 else -1)

Submission status: Accepted

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

ans = []
for i in range(2 ** n):
    tmp1 = [0] * n
    tmp2 = [0] * m
    cost = 0
    for j in range(n):
        if i >> j & 1:
            tmp1[j] = 1
    for j in range(len(tmp1)):
        if tmp1[j] == 1:
            cost += c[j]
            tmp2 = [p+q for p, q in zip(tmp2, a[j])]
    for j in tmp2:
        if j < x:
            break
    else:
        ans.append(cost)

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

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
li =[]
aa = []
for i in range(N):
    la = list(map(int,input().split()))
    li.append(la)
for i in range(2**N):
    lm = [0]*M
    c = 0
    #print(bin(i))
    for j in range(N):
        if  i & (1<<j):
            lm = [lm[a]+li[j][a+1] for a in range(M)]
            c += li[j][0]
            #print(lm)
    #print(lm)
    if all([i>=X for i in lm]):
        #print("a")
        aa.append(c)
if aa == []:
    print("-1")
else:
    print(min(aa))

Submission status: Accepted

Solution code:
def main():
    n, m, x = map(int, input().split())
    ca = []
    for _ in range(n):
        ca.append(list(map(int, input().split())))
    result = 10**9
    for i in range(1, 2**n+1):
        work = 0
        j = 0
        temp = [0] * m
        for flag in bin(i)[2:].zfill(n):
            if flag == "1":
                work += ca[j][0]
                for k in range(1, m+1):
                    temp[k-1] += ca[j][k]
            j += 1
        flag = True
        for t in temp:
            if t < x:
                flag = False
                break
        if flag:
            result = min(result, work)
    if result == 10**9:
        print(-1)
    else:
        print(result)
main()

Submission status: Accepted

Solution code:
import numpy as np
n, m, x = map(int, input().split())

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

# reigaishori
if A.sum(axis=0)[1:].min()<x:
    print(-1)
else:
    kouho=[]
    for i in range(1,2**n):
        tmp=np.array([0]*(m+1))
        for j in range(n):
            if (i>>j)&1:
                tmp=tmp+A[j,]
        if tmp[1:].min()>=x:
            kouho.append(tmp[0])
    print(min(kouho))

Submission status: Accepted

Solution code:
import math


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

ans = math.inf
for i in range(2 ** n):
    rikai = [0 for _ in range(m)]
    p = 0
    for j in range(n):
        if ((i >> j) & 1):
            p += c[j]
            for k, _ in enumerate(rikai):
                rikai[k] += a[j][k]
    if min(rikai) >= x:
        ans = min(ans, p)
if math.isinf(ans):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

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

saisyo = float("inf")
for i in range(2**N):
    a = [0]*M
    gokei = 0
    for j in range(N):
        if (i>>j)&1:
            gokei += A[j][0]
            for k in range(1, M+1):
                a[k-1] += A[j][k]
    if all(a[l] >= X for l in range(M)):
        saisyo = min(saisyo, gokei)

print(saisyo if saisyo != float("inf") else -1)

Submission status: Accepted

Solution code:
n,m,x=[int(j) for j in input().split()]
l=[]
import numpy as np
for i in range(n):
    tmp=[int(j) for j in input().split()]
    l.append((tmp[0],np.array(tmp[1:])))
ans=10**18
for i in range(1<<n):
    tl=np.array([0]*m)
    tc=0
    for j in range(n):
        if i>>j&1:
            c,ll=l[j]
            tc+=c
            tl+=ll
    if len(tl[tl>=x])==m:
        ans=min(ans,tc)

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

Submission status: Accepted

Solution code:
import itertools

N, M, X = [int(i) for i in input().split()]
CA = [] # (C, A)
A = []
for i in range(N):
    c, *a = [int(i) for i in input().split()]
    CA.append((c, a))

min_c = 12 * 10**5 + 1
for x in range(1, N+1):
    for ca in itertools.combinations(CA, x):
        tmp_a = [0 for _ in range(M)]
        tmp_c = 0
        for s in ca:
            tmp_c += s[0]
            tmp_a = [tmp_a[j]+s[1][j] for j in range(M)]
        if min(tmp_a) >= X:
            min_c = min(min_c, tmp_c)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
text = [list(map(int, input().split())) for _ in range(n)]
minmoney = float('inf')
for i in range(2 ** n):
    money = 0
    rikai = [0 for _ in range(m)]
    B = True
    for j in range(n):
        if ((i >> j) & 1):
            money += text[j][0]
            for k in range(m):
                rikai[k] += text[j][k + 1]
    for k in range(m):
        if rikai[k] < x:
            B = False
            break
    if B == True:
        if minmoney >= money:
            minmoney = money
if minmoney == float('inf'):
    print('-1')
    exit()
print(minmoney)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N,M,X = map(int,input().split())

C,A = [],[]
for i in range(N):
  inp = np.array(list(map(int,input().split())))
  #print(inp)
  c = inp[0]
  a = inp[1:]
  C.append(c),A.append(a)

comb = [0,1]
Comb = list(itertools.product(comb, repeat=N))

min_cost = float('inf')
for i in range(len(Comb)):
  tmp = Comb[i]
  tmp_cost = 0
  tmp_u = np.array([0]*M)
  for j in range(N):            
     if(tmp[j] == 1):
       tmp_u += A[j]
       tmp_cost += C[j] 
  
  flag = 1
  for j in tmp_u:
    flag = flag*(X<=j)
  if(flag == 1):      
     min_cost = min(min_cost,tmp_cost)       
                 
if(min_cost == float('inf')):
  print(-1)
else:
  print(min_cost)

Submission status: Accepted

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

ans = 12000000

for i in range(2 ** N):
    c = 0
    und = [0] * M

    for j in range(0, N):
        if (i >> j) & 1:
            c += B[j][0]
            for k in range(M):
                und[k] += B[j][k+1]

    for l in range(M):
        if und[l] < X:
            break
    else:
        ans = min(ans, c)
        continue

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

Submission status: Accepted

Solution code:
import itertools

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

min_price = 10**10
for bit in itertools.product([0, 1], repeat=N):
    temp = [0] * M
    price = 0
    for idx, b in enumerate(bit):
        if b:
            for i, d in enumerate(data[idx][1:]): temp[i] += d
            price += data[idx][0]

    is_valid = True
    for t in temp:
        if t < X:
            is_valid = False
    if is_valid and min_price > price:
        min_price = price

if min_price != 10**10:
    print(min_price)
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np

book_number, algorithm_number, target = map(int, input().split())
price_array = []
book_array = []

for i in range(book_number):
    tmp = list(map(int, input().split()))
    price_array.append(tmp[0])
    book_array.append(tmp[1:len(tmp)])
ans_array = []
for i in range(1, 2**book_number):
    price_bags = []
    book_bags = []
    for j in range(book_number):
        if((i >> j) & 1):
            price_bags.append(price_array[j])
            book_bags.append(np.array(book_array[j]))

    if all(num >= target for num in sum(book_bags)):
        ans_array.append(sum(price_bags))

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

Submission status: Accepted

Solution code:
import itertools

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

p_list = list(itertools.product([0,1], repeat=N))
#print((p_list))
cost_min = 10**9
for p in p_list:
  #p = list(p)
  und=[0]*M
  cost = 0
  for i in range(N):
    if p[i]==1:
      cost += tex[i][0]
      for j in range(M):
        und[j]+=tex[i][j+1]
  #print(und)
  f=True
  for k in range(M):
    if und[k]<X:
      f=False
      break
  if f and cost_min>cost:
    cost_min = cost
    
if cost_min==10**9:
  print(-1)
else:
  print(cost_min)

Submission status: Accepted

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

INF = 10**18
ans = INF
for i in range(2**n):
    ls = [0]*m
    money = 0
    for j in range(n):
        if (i >> j & 1):
            for k in range(m):
                ls[k] += ca[j][k+1]
            money += ca[j][0]
    if min(ls) >= x:
        ans = min(ans, money)

if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

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

ans = float('Inf')
for i in range(2 ** n):
    #print(ans)
    flag = True
    cnt = 0
    s = [0] * m
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m):
                s[k] += cost[j][k + 1]
            cnt += cost[j][0]
    for j in range(m):
        if s[j] < x:
            flag = False
    if flag:
        ans = min(ans, cnt)
if ans != float('Inf'):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C=[];A=[]
for i in range(N):
    inp=list(map(int,input().split()))
    C.append(inp[0])
    A.append(inp[1:])
from itertools import product
ch=[0 for i in range(M)]
ans=10**10
ex=False
for it in list(product([True,False],repeat=N)):
    co=0
    for a in range(M):
        ch[a]=0
    for i in range(N):
        if it[i]:
            co+=C[i]
            for j in range(M):
                ch[j]+=A[i][j]
    ok=True
    for i in range(M):
        if ch[i]<X:
            ok=False
            break
    if ok:
        ans=min(ans,co)
        ex=True
if ex :
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from __future__ import division, print_function
import sys
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
#from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------


n,m,x = mapi()
a =[]
cost = []
for i in range(n):
    tmp = list(mapi())
    cost.append(tmp[0])
    a.append(tmp[1:])
#
res = 0
def check(y):
    for i in y:
        if i<x:
            return False
    return True

def rec(i,arr):
    if check(arr):
        return 0
    if i>=n:
        return float("inf")
    #res= float("inf")
    selct = a[i][:]
    for l in range(m):
        selct[l]+=arr[l]
    return min(cost[i]+rec(i+1,selct),rec(i+1,arr))
tm = [0]*m
res = rec(0,tm)
if res==float("inf"):
    print(-1)
else:
    print(res)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
arr = [list(map(int,input().split())) for i in range(n)]
from itertools import combinations
alg = [0]*m
cost = 99999999
for i in range(1,n+1):
    for com in combinations(range(n),i):
        tmpcost = 0
        alg = [0]*m
        for num in com:
            c = arr[num][0]
            rikai = arr[num][1:]
            tmpcost += c
            alg  = [x + y for (x, y) in zip(alg, rikai)]
        if min(alg)>=x:
            cost = min(cost,tmpcost)

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

Submission status: Accepted

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

ans=[]
for i in range(2**n):
  s=[0]*m
  c=0
  for j in range(n):
    if ((i >> j) & 1):
      for k in range(m):
        s[k]+=l[j][k+1]
      c+=l[j][0]
  t=0
  for j in range(m):
    if s[j]>=x:
      t+=1
  if t==m:
    ans.append(c)

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

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
C,A=[],[]
for i in range(n):
    a=list(map(int,input().split()))
    C.append(a.pop(0))
    A.append(a)
ans=float("inf")
for i in range(n):
    for j in list(itertools.combinations(range(n),i+1)):
        s=0
        R=[0]*m
        for k in j:
            s+=C[k]
            R=[x + y for (x, y) in zip(R, A[k])]
        if all([w>=x for w in R]):
            ans=min(ans,s)
print(-1 if ans == float("inf") else ans)

Submission status: Accepted

Solution code:
import sys
import itertools
import numpy as np
N, M, X = map(int, input().split())
CA = [0 for _ in range(N)]
for i in range(N):
    CA[i] = list(map(int, input().split()))
CA = np.array(CA)

cost = float('inf')
for i in range(1, N + 1):
    L = list(itertools.combinations(CA, i))
    for l in L:
        tmp = sum(l)
        if np.all(tmp[1:] >= X):
            cost = min(cost, tmp[0])
else:
    print(-1 if cost == float('inf') else cost)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N, M, X = map(int, input().split())

book = []
for _ in range(N):
    tmp = [int(i) for i in input().split()]
    book.append(tmp)

# print(book)


lis = list(range(N))
result = []
for n in range(1, len(lis)+1):
    for conb in itertools.combinations(lis, n):
        result.append(list(conb))  # タプルをリスト型に変換
# print(result)

ans = []

for com in result:
    # print(com)
    l = len(com)
    s_skill = np.array([0] * M)
    money = 0
    for idx in com:
        money += book[idx][0]
        s_skill += np.array(book[idx][1:])

    flg = True
    for i in s_skill:
        if i < X:
            flg = False
    ans.append([flg, money])

# print(ans)

output = -1
b_flg = False
for i in ans:
    b = i[0]
    money = i[1]
    if b:
        b_flg = True
        if output == -1:
            output = money
        output = min(output, money)

if not b_flg:
    print(-1)
else:
    print(output)

Submission status: Accepted

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

lis = []
for i in range(n):
  li = list(map(int, input().split()))
  lis.append(li)
  
anss = [0]*2**n
for i in range(2**n):
  rikaido = [0]*m
  for j in range(n+1):
    if str(bin(i)[-j-1]) == "1":
      anss[i] += lis[j][0]
      for k in range(m):
        rikaido[k] += lis[j][k+1]
    elif str(bin(i)[-j-1]) == "b":
      for k in range(m):
        if rikaido[k] < x:
          anss[i] = 0
      break

ans = 10**10
for i in range(2**n):
  if anss[i] > 0:
    ans = min(ans, anss[i])

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

Submission status: Accepted

Solution code:
from itertools import product

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

a = []
c = []

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

ans = []
for b in product([0, 1], repeat=N):
    total = 0
    lrn = [0] * M
    for k, i in enumerate(b):
        total += i * c[k]
        for j in range(M):
            lrn[j] += a[k][j]*i

    if min(lrn) >= X:ans.append(total)
print(-1 if ans==[] else min(ans))

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
ans=[]
c=[]
for _ in range(N):
    c.append(list(map(int, input().split())))
for i in range(pow(2,N)):
    d=[0]*(M+1)
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(M+1):
                d[k]+=c[j][k]
    j=True
    for l in range(1,M+1):
        if d[l]<X:
            j=False
    if j:
        ans.append(d[0])
if len(ans)!=0:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
cin = open(0).read().strip().split('\n')
n,m,x = map(int, cin[0].split(' '))
books = []
for i in cin[1:]:
    books.append(tuple(map(int, i.split(' '))))

money = float('inf')
for i in range(2**n):
    ret = [0] * m
    tmp_money = 0
    for j in range(n):
        if i >> j & 1:
            for mi in range(m):
                ret[mi] += books[j][1+mi]
            tmp_money += books[j][0]
    if min(ret) >= x:
        money = min(money, tmp_money)

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