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:
import itertools
n,m,x=map(int,input().split())
C=[]
for i in range(n):
    a=list(map(int,input().split()))
    C.append(a)
pattern=[]
#toBuy=[]
for i in range(n+1):
    toBuyc=list(itertools.combinations(C,i))
    for j in range(len(toBuyc)):
    #    print(toBuyc[j])
        pattern.append(toBuyc[j])
   # print(pattern)
"""for i in range(2**n):
    toBuy=[]
    for j in range(n):
        if ((i>>j)&1):
            toBuy.append(C[j])"""
   # print(toBuy)
    #pattern.append(toBuy)
#print(pattern)
X=[0]*m #mつのアルゴリズムそれぞれの経験値
xsum=0#とりあえずはじくためのやつ
sum=0#値段
min=12000000 
check=0
for tb in pattern:#toBuyについて
    sum=0
    xsum=0
    X=[0]*m
    for c in tb:
        for j in range(len(c)):
            if j==0:
                sum+=c[j]#price
            else:
                xsum+=c[j]#経験値そうごう
                X[j-1]+=c[j]#経験値各自
    if xsum<x*m:
        continue
    else:
        for eX in X:
            if eX<x:
                check=1
        if check==1:
            check=0
            continue
        if sum<min:
            min=sum
if min==12000000:
    print(-1)
else:
    print(min)

Submission status: Accepted

Solution code:
from sys import maxsize
import numpy as np


def check(ls, x):
    for i in range(1, len(ls)):
        if ls[i] < x:
            return False
    return True


n, m, x = map(int, input().split())
ls = []
a = [i for i in range(n)]
for i in range(n):
    ls.append(list(map(int, input().split())))
dp = [np.zeros(m + 1) for i in range((1 << n))]
for i in range(n):
    dp[1 << i] = np.array(ls[i])
total_cost = maxsize
for subset in range(1, (1 << n)):
    for i in range(n):
        if subset & (1 << i):
            dp[subset] = np.add(dp[subset ^ (1 << i)], dp[(1 << i)])
    if check(dp[subset], x):
        total_cost = min(total_cost, dp[subset][0])
if total_cost == maxsize:
    print(-1)
else:
    print(int(total_cost))

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
CA=[list(map(int,input().split())) for _ in range(N)]
#print(CA)
cost_0 = 10000000
b = f"0{N}b"
for i in range(2**N):
    i_bit = str(format(i,b))
    #print(i_bit)
    Ans = [0]*(M+1)
    for j in range(N):
        if i_bit[j] == "1":
            Ans = [p+ca for p,ca in zip(Ans,CA[j])]
    if min(Ans[1:])>=X:
        cost = Ans[0]
    else:
        cost = cost_0
    cost_0 = min(cost_0,cost)
if cost_0 != 10000000:
    print(cost_0)
else:
    print(-1)

Submission status: Accepted

Solution code:
def saiki(N,M,X,check,book,cost):
	if len(check) == N:
		u = [0] * M
		c = 0
		for i in range(N):
			if check[i] == 1:
				b = book[i]
				c += b[0]
				for j in range(1,M+1):
					u[j-1] += b[j]
		if min(u) >= X:
			if cost[0] == -1 or cost[0] > c:
				cost[0] = c
	else:
		C = check[:]
		saiki(N,M,X,C+[0],book,cost)
		C = check[:]
		saiki(N,M,X,C+[1],book,cost)

if __name__ == '__main__':
	N,M,X = map(int, input().split())
	book = []
	for _ in range(N):
		book.append([int(a) for a in input().split()])

	cost = [-1]
	saiki(N,M,X,[],book,cost)

	print(cost[-1])

Submission status: Accepted

Solution code:
from itertools import product
n, m, x = map(int,input().split())
A = []
C = []
for i in range(n):
    a = list(map(int,input().split()))
    C.append(a[0])
    A.append(a[1:])

total = float('inf')
ok = False
for pr in product([0, 1], repeat=n):
    clct = 0
    for a in zip(*A):
        cnt = 0
        for i in range(n):
            if pr[i] == 1:
                cnt += a[i]
        if cnt >= x:
            clct += 1
    
    if clct == m:
        ok = True
        ttl = 0
        for c,p in zip(C, pr):
            if p == 1:
                ttl += c
        total = min(total, ttl)

if ok:
    print(total)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
lis=tuple(tuple(map(int,input().split())) for _ in range(n))
ans=float("inf")

def dfs(progress,skills,nowcost):
    global ans
    if progress==n:
        if all(v>=x for v in skills):
            ans=min(ans,nowcost)
        return ans
    dfs(progress+1,skills,nowcost)
    dfs(progress+1,[a+b for a,b in zip(skills,lis[progress][1:])],nowcost+lis[progress][0])

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = []
bit = 0
for i in range(n):
    c.append(list(map(int,input().split())))
ans = 1000000000000
for i in range(2**n):
    l = [0 for _ in range(m)]
    current = 0
    for j in range(n):
        if (i>>j)&1:
            current += c[j][0]
            for k in range(m):
                l[k] += c[j][k+1]
    flag = 1
    for h in l:
        if h < x:
            flag = 0
    if flag:
        ans = min(ans,current)
if ans == 1000000000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import itertools
N,M,X=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(N)]
ans=9999999999
 
V=list(itertools.product([0,1], repeat=N))
 
for v in V:
  cost=0
  C=[0]*M
  for n in range(N):
    if v[n]==1:
      cost += arr[n][0]
      for j in range(1,M+1):
        C[j-1] += arr[n][j]
      
  if min(C) >= X:
    ans=min(ans,cost)
    
if  ans ==  9999999999: 
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

INF = 10**9
ans = INF

for s in range(0,1 << n):
    smart = [0] * m
    cost_sum = 0
    for i in range(n):
        if (s >> i) % 2 == 0:
            continue
        cost_sum += c[i]
        for j in range(m):
            smart[j] += A[i][j]
    ok = True
    for j in range(m):
        if smart[j] < x:
            ok = False
    if ok:
        ans = min(cost_sum,ans)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
C=[]
for i in range(n):
    a=list(map(int,input().split()))
    C.append(a)
pattern=[]
toBuy=[]
for i in range(2**n):
    toBuy=[]
    for j in range(n):
        if ((i>>j)&1):
            toBuy.append(C[j])
 #   print(toBuy)
    pattern.append(toBuy)
#print(pattern)
X=[0]*m #mつのアルゴリズムそれぞれの経験値
xsum=0#とりあえずはじくためのやつ
sum=0#値段
min=12000000 
check=0
for tb in pattern:#toBuyについて
    sum=0
    xsum=0
    X=[0]*m
    for c in tb:
        for j in range(len(c)):
            if j==0:
                sum+=c[j]#price
            else:
                xsum+=c[j]#経験値そうごう
                X[j-1]+=c[j]#経験値各自
    if xsum<x*m:
        continue
    else:
        for eX in X:
            if eX<x:
                check=1
        if check==1:
            check=0
            continue
        if sum<min:
            min=sum
if min==12000000:
    print(-1)
else:
    print(min)

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
lis=tuple(tuple(map(int,input().split())) for _ in range(n)) #再代入しないので二次元tupleでよい
ans=float("inf")

def dfs(progress,skills,nowcost):#実行前においておけば参照できる
    global ans
    if progress==n:
        if all(v>=x for v in skills):
            ans=min(ans,nowcost)
        return 0
    dfs(progress+1,skills,nowcost)
    dfs(progress+1,[a+b for a,b in zip(skills,lis[progress][1:])],nowcost+lis[progress][0])

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

Submission status: Accepted

Solution code:
from itertools import product

N, M, X = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]
ans = float("inf")

for now in product(range(2), repeat=N):
    res = 0
    An = [0 for _ in range(M)]
    for n in range(N):
        if now[n] == 1:
            res += A[n][0]
            An = [An[j] + A[n][j+1] for j in range(M)]
    if min(An) >= X:
        ans = min(ans, res)

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

Submission status: Accepted

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

for i in range(2**N):
  cost=0
  C=[0]*M
  for n in range(N):
    #右にずらして一桁目が1かどうかを判定
    if (i>>n) &1:
      cost += arr[n][0]
      for j in range(1,M+1):
        C[j-1] += arr[n][j]
  if min(C)>=X:
    ans=min(ans, cost)
    
if ans ==  9999999999:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

matrix = []
c = []
ans = float("inf")

for i in range(N):
    matrix.append(list(map(int, input().split())))
    c.append(matrix[i].pop(0))

for i in range(2 ** N):
    cost = 0
    rikai = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            cost += c[j]
            for k in range(M):
                rikai[k] += matrix[j][k]
    flg = True
    for k in range(M):
        if rikai[k] < X:
            flg = False
    if flg:
        ans = min(ans, cost)
    

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

Submission status: Accepted

Solution code:
import logging

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)


def main():
    N, M, X = map(int, input().split())
    CA_list = [list(map(int,list(input().split(" ")))) for i in range(N)]
    Ci_sum_list = []
    
    for i in range(2 ** N):
        sum_list = [0 for i in range(M + 1)]
        for j in range(N):
            if ((i >> j) & 1):
                sum_list = [x + y for (x, y) in  zip(sum_list, CA_list[j])]
                
        logging.info(sum_list)
        if [x for x in sum_list[1:] if x < X]:
            continue
        else:
            Ci_sum_list.append(sum_list[0])

    if Ci_sum_list:
        print(min(Ci_sum_list))
    else:
        print(-1)
        
if __name__ == "__main__":
    main()

Submission status: Accepted

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

ans = float('inf')
def dfs(step, m_list, cost):
    global ans
    if all(elem>=x for elem in m_list):
        ans = min(cost, ans)
    elif step != n:
        dfs(step+1, m_list, cost)
        m_list = [x+y for x, y in zip(m_list, a[step][1:])]
        cost += a[step][0]
        dfs(step+1, m_list, cost)

dfs(0, [0]*m, 0)
print(-1 if ans==float('inf') else ans)

Submission status: Accepted

Solution code:
def check(learn_total):
    for i in range(m):
        if learn_total[i] < x:
            return False
    return True


def calc_price(bit):
    price_total = 0  # 値段の合計
    learn_total = [0] * m  # 理解度

    for i in range(n):
        if (bit >> i) & 1:  # i桁目が0か1か見て、i番目を買うか買わないか判定します
            price_total += c[i]  # 買うので、i番目の値段を加算します
            learn = a[i]  # 「i番目の参考書を読んで増える、各アルゴリズムの理解度」のリストです
            for j, le in enumerate(learn):  # 理解度を足します。 enumerateを使うと、range(n)よりスマートです
                learn_total[j] += le

    # 条件を満たすか、check関数で確認します
    if check(learn_total):
        return price_total
    else:
        return INF


if __name__ == '__main__':
    INF = float("inf")

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

    # 空のリストを作って、appendで追加していきます
    c = []  # 参考書の値段です
    a = []  # 各参考書に入る理解度です

    for i in range(n):
        c_temp, *a_temp = list(map(int, input().split()))  # こうすると、2つ目以降をリストで受け取れます
        c.append(c_temp)
        a.append(a_temp)

    ans = INF

    for bit in range(1 << n):
        price = calc_price(bit)  # 条件を満たすなら価格、満たさないならINFが返ってきます
        ans = min(ans, price)  # 答えを更新します

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
A = []
for i in range(N):
  A.append(list(map(int, input().split())))
min = -1
for i in range(1, 2**N):
  x = []
  for j in range(M):
    x.append(0)
  c = 0
  chk = True
  for j in range(N):
    b = bin(i & 2**j)
    if b[2] == "1":
      c += A[j][0]
      for k in range(M):
        x[k] += A[j][k+1]
  for l in range(M):
    if x[l] < X:
      chk = False
      break
  if chk == False:
    continue
  if min == -1:
    min = c
  elif c < min:
    min = c
print(min)

Submission status: Accepted

Solution code:
from itertools import product as pr
n,m,x=[int(i) for i in input().split()]
l=[[int(i) for i in input().split()]for j in range(n)]
p=list(pr([0,1],repeat=n))
suml=[[sum([l[j][k]*i[j] for j in range(n)])for k in range(m+1)]for i in p]
ans=[i[0] for i in suml if all([i[j] >=x for j in range(1,m+1)])]
if len(ans)==0:
  print(-1)
else:
  print(min(ans))

Submission status: Accepted

Solution code:
import numpy as np

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

ans = float('inf')
for i in range(2 ** n):
    cost = 0
    exp = np.array([0] * m)
    for j , b in enumerate(books):
        if i >> j & 1: continue
        cost += b[0]
        exp = exp + np.array(b[1:])
    if (exp < x).any(): continue
    ans = min(cost, ans)

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [list(map(int, input().split())) for i in range(n)]
ans = float("INF")

for i in range(1 << n):
    costs = 0
    understand = [0] * m
    for j in range(n):
        if i >> j & 1:
            costs += c[j][0]
            for k in range(m):
                understand[k] += c[j][k + 1]
    if min(understand) >= x:
        ans = min(ans, costs)
    
print(ans) if ans != float("INF") else print(-1)

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
lis=tuple(tuple(map(int,input().split())) for _ in range(n)) #再代入しないので二次元tupleでよい
ans=float("inf")

for choice in itertools.product(range(2),repeat=n):#0,1のbit全探索
    cost=0
    skills=[0]*m
    for flag,book in zip(choice,lis):
        if flag:
            C,A = book[0],book[1:]
            cost += book[0]
            for i,a in enumerate(A):
                skills[i]+=a
    if all(v>=x for v in skills):
        ans=min(ans,cost)
if ans==float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
cam = [list(map(int, input().split())) for i in range(n)]
ans=10000**12

for i in range(2**n):
    a=[0]*m
    cst=0
    for j in range(n):
        bag=[]
        if (i>>j)&1:
            cst+=cam[j][0]
            for k in range(1,m+1):
                a[k-1]+=cam[j][k]
    if all(elem >= x for elem in a):
        ans=min(ans,cst)
    
if ans<10000**12:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
books = [[*map(int, input().split())] for _ in range(n)]
ans = inf = 10**18
for bit in range(1<<n): #  [0,(2^N)-1] combination full search
    cost = 0
    skill = [0]*m
    for book in range(n): # [0,N-1] book no.
        if(bit>>book & 1): # buy
            cost += books[book][0] # cost get
            skill = [*map(lambda x,y: x+y, skill, books[book][1:])] # skill get
    if min(skill) >= x: ans = min(ans, cost) # skill check
if ans == inf: ans = -1 # exist?
print(ans)

Submission status: Accepted

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

ans = float('inf')
exist = False
for bit in range(1 << N):
    flag = True
    S = [0]*M
    sumnum = 0
    for i in range(N):
        if bit & (1 << i):
            sumnum += C[i]
            for j in range(M):
                S[j] += A[i][j]

    for k in range(M):
        if S[k] < X:
            flag = False
            break
    if flag:
        ans = min(ans, sumnum)
    
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
books = [[*map(int, input().split())] for _ in range(n)]
ans = inf = 10**18
for bit in range(1<<n): #  [0,(2^N)-1] full search
    cost = 0
    skill = [0]*m
    for book in range(n): # [0,N-1] book no.
        if(bit>>book & 1): # buy
            cost += books[book][0]
            for j in range(m): skill[j] += books[book][j+1] # skill get
    if min(skill) >= x: ans = min(ans, cost)
if ans == inf: ans = -1
print(ans)

Submission status: Accepted

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

import numpy as np

A=[]
B=[]

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


C=[]
temp=[0 for i in range(N)]

for i in range(2**N):
  for j in range(N):
    if (i >> j) & 1:
      temp[j]=1
    else:
      temp[j]=0
  tempE=[0 for i in range(M+1)]
  for k in range(N):
    x = np.array(tempE)
    y = np.array([A[k][j]*temp[k] for j in range(M+1)])
    tempE=x+y
  C.append(tempE)


tempC=float('inf')
for i in range(2**N):
  tempD=min(C[i][1:M+1])
  if tempD>=X:
    tempC=min([tempC,C[i][0]])

if tempC==float('inf'):
  tempC=-1

print(tempC)

Submission status: Accepted

Solution code:
import itertools

n, m, x = map(int, input().split())
book = [list(map(int, input().split())) for i in range(n)]
count = 0
min_total=100000000

for i in range(2 ** n):
    subtotal = 0
    tmp_rikaido=[0]*m
    for j in range(n):
        if (i >> j) & 1:
            subtotal+=book[j][0]
            for k in range(m):
                tmp_rikaido[k] += book[j][k + 1]
                if all(a >= x for a in tmp_rikaido):
                    count += 1
                    if min_total > subtotal:
                        min_total=subtotal

if count == 0:
    print(-1)
else:
    print(min_total)

Submission status: Accepted

Solution code:
from itertools import product
from itertools import combinations
import numpy as np

def resolve():
  N, M, X = map(int, input().split(" "))

  books = []
  for i in range(N):
    CA = [int(x) for x in input().split(" ")]
    books.append(CA)

  books = np.array(books)


  if N == 1:
    if np.all(books[:, 1:] >= X):
      print(books[0][0])
    else:
      print(-1)
    return True
  books_index_pattarns = [list(x) for i in range(1, N+1) for x in combinations(range(0, N), i)]
  books_result = np.array([np.sum(books[x], axis=0) for x in books_index_pattarns])
  books_result = books_result[np.all(books_result[:,1:] >= X, axis=1)]

  if len(books_result) == 0:
    print(-1)
    return True
  elif len(books_result) == 1:
    print(books_result[0][0])
    return True
  else:
    # print(books_result)
    print(books_result[:,:1].min())
    return True

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
c = [0]*n
a = [[]]*n
for i in range(n):
    d = [*map(int, input().split())]
    c[i] = d[0]
    a[i] = d[1:]
ans = inf = 10**18

for bit in range(1<<n): #  [0,(2^N)-1] full search
    cost = 0
    skill = [0]*m
    for book in range(n): # [0,N-1] book no.
        if(bit>>book & 1): # buy
            cost += c[book]
            for j in range(m): skill[j] += a[book][j] # skill get
    if min(skill) >= x: ans = min(ans, cost)
if ans == inf: ans = -1
print(ans)

Submission status: Accepted

Solution code:
# from itertools import combinations

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

# L = []
# for _ in range(N):
#     L.append(list(map(int, input().split())))

# s = float('inf')
# r = False

# for i in range(1, N + 1):
#     C = combinations(range(0, N), i)
#     for c in C:
#         _s = 0
#         t = [0 for _ in range(M)]
#         for _c in c:
#             _s += L[_c][0]
#             for k in range(M):
#                 t[k] += L[_c][k + 1]
#         _r = True
#         for _t in t:
#             if _t < X:
#                 _r = False
#                 break
#         if _r and _s < s:
#             r = True
#             s = _s
# if r:
#     print(s)
# else:
#     print(-1)

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

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

s = float('inf')
r = False

for i in range(2 ** N):
    _s = 0
    t = [0 for _ in range(M)]
    for k in range(N):
        if (i >> k & 1):
            _s += L[k][0]
            for j in range(M):
                t[j] += L[k][j + 1]
    _r = True
    for _t in t:
        if _t < X:
            _r = False
            break
    if _r and _s < s:
        r = True
        s = _s
if r:
    print(s)
else:
    print(-1)

Submission status: Accepted

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+1):
  if sums[i] < X:
    OK = False
    break

if OK == False:
  print(-1)
else:
  As = []
  for A in combinations_with_replacement(range(0, N),N):
    As.append(tuple(set(A)))
  As = list(map(list, set(As)))
  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+1):
      if sums[k] < X:
        OK2 = False
        break
    if OK2 == True and sums[0] < min_:
      min_ = sums[0]
  print(min_)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
# print(n,m,x)
c = [0]*n
a = [[]]*n
# print(a)
for i in range(n):
    d = [*map(int, input().split())]
    c[i] = d[0]
    a[i] = d[1:]
    # print(x)
# print(c)
# print(a)
ans = inf = 10**18

for bit in range(1<<n): #  [0,(2^N)-1] full search
    cost = 0
    skill = [0]*m
    for book in range(n): # [0,N-1] book no.
        # print(book, bit, bit>>(n-1-book))
        if(bit>>book & 1): # buy
            cost += c[book]
            for j in range(m):
                skill[j] += a[book][j] # skill get
    # print(skill)
    # print(cost)

    # ok = True
    # for s in skill:
    #     if s < x:
    #         ok = False
    #         break
    # if ok: ans = min(ans, cost)
    if min(skill) >= x: ans = min(ans, cost)
# print(ans,inf)
if ans == inf: ans = -1
print(ans)

Submission status: Accepted

Solution code:
from sys import maxsize
import numpy as np


def check(ls, x):
    for i in range(1, len(ls)):
        if ls[i] < x:
            return False
    return True


def convert(b, n):
    diff = n - len(b)
    return ('0' * diff + b)[::-1]


n, m, x = map(int, input().split())
ls = []
a = [i for i in range(n)]
for i in range(n):
    ls.append(list(map(int, input().split())))
dp = [0] * ((1 << n) + 1)
for i in range(n):
    dp[1 << i] = np.array(ls[i])
total_cost = maxsize
for subset in range(1, (1 << n)):
    b = bin(subset)[2:]
    b = convert(b, n)
    a = np.zeros(m + 1)
    for i in range(n):
        if int(b[i]):
            a += dp[1 << i]
    dp[subset] = a
    if check(dp[subset], x):
        total_cost = min(total_cost, dp[subset][0])
if total_cost ==maxsize:
    print(-1)
else:  
    print(int(total_cost))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


def dfs(i, res, under):
    if i == n:
        if min(under) < x:
            return -1
        else:
            return res
    l = dfs(i + 1, res + c[i], [s + t for (s, t) in zip(under, a[i])])
    r = dfs(i + 1, res, under)
    if l == r == -1:
        return -1
    else:
        if l == -1:
            return r
        elif r == -1:
            return l
        else:
            return min(l, r)


n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
c = [a[s][0] for s in range(n)]
a = [a[t][1:] for t in range(n)]
und = [0]*m
ans = []
print(dfs(0, 0, und))

Submission status: Accepted

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+1):
  if sums[i] < X:
    OK = False
    break

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
a = [[] for i in range(n)]
c = [0] * n
for i in range(n):
	c[i], *a[i] = map(int, input().split())
ans = 1e9
for mask in range(2 ** n):
	cost = 0
	b = [0] * m
	for i in range(n):
		if mask & (1 << i):
			cost += c[i]
			for j in range(m):
				b[j] += a[i][j]
	cnt = True
	for j in range(m):
		cnt &= b[j] >= x
	if cnt:
		ans = min(ans, cost)
			
if ans < 1e9:
	print(ans) 
else:
	print(-1)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

N, M, X = list(map(int, input().split()))
conditions = product([0, 1], repeat=N)
A = np.array([list(map(int, input().split())) for i in range(N)])
succeed = []
for c in conditions:
    p = A * np.array(c).reshape((N, 1))
    res = p.sum(axis=0)
    if np.all(res[1:] >= X):
        succeed.append(res[0])
print(min(succeed) if len(succeed) > 0 else -1)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

# 入力はstringで入る．
# intにしたければ int(input())
# floatで受け取ると 1.0 になる．

import numpy as np

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

CAarray = np.array(CA)
C = CAarray[:,0]
A = CAarray[:,1:M+2]

if np.count_nonzero(np.sum(A, axis=0) < X) != 0:
    print(-1)
    exit()

Answer = np.sum(C)

for i in range(0,2**N):
    ll = [int(x) for x in list(str(format(i,'b').zfill(N)))]
    l = np.array(ll)

    if np.count_nonzero(np.dot(A.T,l.T) >= X) == M:
        if Answer >= np.dot(C.T,l.T):
            Answer = np.dot(C.T,l.T)

print(Answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M, X = [int(x) for x in input().split()]
    C = []
    A = []
    for i in range(N):
        tmp = [int(x) for x in input().split()]
        C.append(tmp[0])
        A.append(tmp[1:])
    CA = [[C[i], v] for i, v in enumerate(A)]

    # TLE
    # l = list(itertools.permutations(CA, N))
    # anss = [100100100] * len(l)
    # for i, v in enumerate(l):
    #     arr = [0] * M
    #     s = 0
    #     for j in v:
    #         arr = python_list_add(arr, j[1])
    #         s += j[0]
    #         if all([x >= X for x in arr]):
    #             anss[i] = s
    #             break
    # ans = min(anss)
    # if ans == 100100100:
    #     print(-1)
    #     return
    # print(ans)

    # bit全探索
    anss = []
    for i in range(2 ** N):
        s = 0
        arr = [0] * M
        for j in range(N):
            if i >> j & 1:
                s += CA[j][0]
                arr = python_list_add(arr, CA[j][1])
            if all([x >= X for x in arr]):
                anss.append(s)
    print(min(anss) if anss else -1)

    return


def python_list_add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]


if __name__ == '__main__':
    main()

Submission status: Accepted

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+1):
  if sums[i] < X:
    OK = False
    break

if OK == False:
  print(-1)
else:
  # As = []
  # for A in combinations_with_replacement(range(0, N), r=M):
  #   As.append(tuple(set(A)))
  # As = list(map(list, set(As)))
  min_ = sums[0]
  hoge = []
  kouho = list(range(1,N+1))
  for i in combinations_with_replacement(kouho, N):
    hoge.append(list(set(i)))
  hoge = list(map(list, set(map(tuple, hoge))))
  for i in hoge:
    mini_CA = []
    for j in i:
      mini_CA.append(CA[j-1])
    mini_CA = np.array(mini_CA)
    OK2 = True
    sums = np.sum(mini_CA,axis=0)
    for k in range(1,M+1):
      if sums[k] < X:
        OK2 = False
        break
    if OK2 == True and sums[0] < min_:
      min_ = sums[0]
  print(min_)

Submission status: Accepted

Solution code:
if __name__=="__main__":
    N, M, X = map(int, input().split(' '))
    book_list = [None]*N
    min_price = -1
    for i in range(N):
        book_list[i] = list(map(int, input().split(' ')))

    for i in range(2 ** N):
        comp_list = []
        for j in range(N):
            if ((i >> j) & 1):
                if comp_list == []:
                    comp_list = book_list[j]
                else:
                    comp_list = [a + b for a, b in zip(comp_list, book_list[j])]

                if all(comp >= X for comp in comp_list[1:]):
                    if min_price == -1:
                        min_price = comp_list[0]
                    elif comp_list[0] <= min_price:
                        min_price = comp_list[0]
    print(min_price)

Submission status: Accepted

Solution code:
import numpy as np

n,m,x = (int(x) for x in input().split())
C=[]
A=[]
for i in range(n):
    c,*a = (int(x) for x in input().split())
    C.append(c)
    A.append(a)

buy = [{"c":0,"a":np.zeros(m)}]
for i in range(len(C)):
    temp = []
    for j in buy:
        temp.append(j)
        temp.append({"c":j["c"]+C[i],"a":j["a"]+np.array(A[i])})
    buy = temp

#print(buy)
    
res = 10**7
for i in buy:
    if np.all(i["a"]>=x):
        res = min(i["c"],res)
if res == 10**7:
    res = -1
    
print(res)