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 sys
input = sys.stdin.readline


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

    MONEY = []
    UNDERSTAND = []
    for i in range(n):
        lst = [int(i) for i in input().split()]
        MONEY.append(lst[0])
        UNDERSTAND.append(lst[1:])

    ans = -1
    for i in range(1 << n):
        understand = [0] * m
        money = 0
        for j in range(n):
            if (i >> j) & 1 == 0:
                continue
            money += MONEY[j]
            for k in range(m):
                understand[k] += UNDERSTAND[j][k]
        if all([i >= x for i in understand]):
            if ans == -1:
                ans = money
            else:
                ans = min(ans, money)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ca = [list(map(int,input().split())) for i in range(n)]
sum = [list([0] * (m+1)) for i in range(2**n)]

min_value = -1

for i in range(2**n):
    flg = 0
    for j in range(n):
        if i & 2**j:
            sum[i][0] += ca[j][0]
            for k in range(m):
                sum[i][k+1] += ca[j][k+1]
    for k in range(m):
        if (sum[i][k+1] < x):
            flg = 1
            break

    if (sum[i][0] < min_value or min_value == -1) and flg == 0:
        min_value = sum[i][0]

print(min_value)

Submission status: Accepted

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

book_list = [tuple(map(int, input().strip().split())) for _ in range(N)]

most_cheep = 10**7
for pattern in range(1 << N):
    understanding_list = [0]*M
    cost_list = []
    for n_bit in range(N):
        if (pattern >> n_bit)&1:
            for m in range(M):
                understanding_list[m] += book_list[n_bit][m+1]
            cost_list.append(book_list[n_bit][0])
    for understanding in understanding_list:
        if understanding < X:
            break
    else:
        most_cheep = min(most_cheep, sum(cost_list))

if most_cheep == 10**7: most_cheep=-1

print(most_cheep)

Submission status: Accepted

Solution code:

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

A = [[0]*M]*N
temp = [0]*(M+1)
C = [0]*N

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

clear = 0
hoge = [int(x) for x in range(0,N)]
min_total = sum(C)

for i in range(2**len(hoge)):
    bag = []
    for j in range (len(hoge)):
        if (i>>j)&1:
            bag.append(hoge[j])
    total =0
    
    skil=[0]*M
    master=[0]*M
#    print(bag)
    for b in bag:
        total += C[b]
        for m in range (0,M):
            skil[m] += A[b][m]
            if skil[m]>=X:
                master[m] +=1
        if 0 not in master :
            min_total = min(min_total,total)
            clear += 1
#        print(skil)
    
if clear >0:
    print(min_total)
else:
    print('-1')

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    tmp = list(map(int, input().split()))
    C.append(tmp[0])
    A.append(tmp[1:])
ans = float('INF')
level = [0] * M
def DFS(cost, level_list, start):
    global ans
    if min(level_list) >= X:
        ans = min(ans, cost)
        return ans
    # 処理
    for i in range(start, N):
        tmp_cost = cost + C[i]
        tmp_level_list = [x + y for (x, y) in zip(level_list, A[i])]
        DFS(tmp_cost, tmp_level_list, i + 1)
    return ans

ans = DFS(0, level, 0)
if ans != float('INF'):
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

ans = float("inf")

for comb in range(2**N):
    cost = 0
    learned = [0]*(M)

    for i in range(N):
        if (comb >> i) & 1:
            cost += lst[i][0]
            for j in range(0, M):
                learned[j] += lst[i][j+1]


    if min(learned)>=X: ans = min(ans,cost)

if ans > 100000*N:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N,M,X=[int(x) for x in input().split()]
L=[]
for _ in range(N):
  L.append([int(x) for x in input().split()])

Smin=-1
for i in range(N):
  for t in combinations(L,i+1):
    S=0
    A=[0]*M
    for l in t:
      S+=l[0]
      for x in range(M):
        A[x]+=l[1+x]
    ok=True
    for x in range(M):
      if A[x] < X:
        ok=False
        break
    if ok and (Smin==-1 or Smin>S):
      Smin=S
print(Smin)

Submission status: Accepted

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

C=[]
A=[]
for i in range(n):
	t = list(map(int, input().split()))
	C.append(t[0])#price of books
	A.append(t[1:])#point of books
	
result = 10**9 #結果の初期値
#N冊の本買う/買わない　を総当たり
for i in range(1<<n):#range(0,2**n)と同意
	t = [0] * m #理解度m個
	c = 0 #値段0
	#1-n冊目までをシフト演算
	for j in range(n):
		if (i>>j)&1:#購入している場合
			for k in range(m):
				t[k] += A[j][k]#各理解度をインプット
			c += C[j] #購入した本の値段を足していく
		else:
			pass
	if min(t)>=x:
		result=min(result, c)
if result == 10**9:
	print(-1)
else:
	print(result)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
add=[]
for i in range(2**n):
    skill=[0]*(m+1)
    for j in range(n):
        if ((i>>j)&1):
            skill=list(map(sum,zip(skill,l[j])))
    if min(skill[1:])>=x:
        add.append(skill)
if add:
    add.sort()
    print(add[0][0])
else:
    print(-1)

Submission status: Accepted

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

#A = np.zeros((n, m))
CA = np.zeros((n,m+1))

for i in range(n):
    CA[i]=list(map(int, input().split()))
    # C[i],A[i]=T[0],T[1:]
#print(A,C)

min_cost = -1

for i in range(2**n):
    T = np.zeros((m+1))
    for j in range(n):
        if i&(2**j) > 0:
            T += CA[j]
    if all(T[1:] >= x):
        if min_cost == -1:
            min_cost = T[0]
        else: 
            min_cost = min(min_cost,T[0])        

print(int(min_cost))

Submission status: Accepted

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

ans = float('inf')
flg = 0

for i in range(2 ** n):
    chk = [0] * (m + 1)
    for j in range(n):
        if i >> j & 1:
            for k in range(m + 1):
                chk[k] += lst[j][k]
    if all([chk[i] >= x for i in range(1, m + 1)]):
        ans = min(ans, chk[0])
        flg = 1

print(ans if flg else '-1')

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(N)]
ans = 10**18

for S in range(2**N):
    ans_cand = 0
    now = [0]*M
    
    for i in range(N):
        if (S>>i)&1:
            ans_cand += l[i][0]
            
            for j in range(1, M+1):
                now[j-1] += l[i][j]
    
    if min(now)>=X:
        ans = min(ans, ans_cand)

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

Submission status: Accepted

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

def check(ary, m, x):
  for i in range(1, m+1):
    if ary[i] < x:
      return False
  return True


#
#

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

#start = time.time()

ans = -1
records = []
for i in range(0, n):
  ary = list(map(int, input().split()))

  if 0 < ans and ans <= ary[0]:
    continue

  next_records = []

  if check(ary, m, x):
    ans = ary[0]
  else:
    next_records.append(ary)

  for rec in records:
    if 0 < ans and ans <= ary[0] + rec[0]:
      continue
    dst = [ ary[i] + rec[i] for i in range(0, m+1)]
    if check(dst, m, x):
      ans = dst[0]
    else:
      next_records.append(dst)

  if i == n - 1:
    break

  if ans < 0:
    records = records + next_records
  else:
    new_records = []
    for rec in records:
      if rec[0] < ans:
        new_records.append(rec)
    for rec in next_records:
      if rec[0] < ans:
        new_records.append(rec)
    records = new_records

  #print(records)

print(ans)

#elapsed_time = time.time() - start
#print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Submission status: Accepted

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

min_cost = 10000000 * n
for i in range(1, 2 << n-1):
    a_total = [0] * m
    cost = 0
    p = list(format(i, 'b').zfill(n))
    for j in range(len(p)):
        if p[j] == '1':
            a_total = [a + b for a, b in zip(a_total, c[j][1:])]
            cost += c[j][0]
    for a in a_total:
        if a < x:
            break
    else:
        min_cost = min(cost, min_cost)

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

Submission status: Accepted

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

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

min_cost = 10000000 * n
for i in range(1, 2 << n-1):
    a_total = []
    cost = 0
    for l in range(m):
        a_total.append(0)
    p = list(format(i, 'b').zfill(n))
    for j in range(len(p)):
        if p[j] == '1':
            a_total = [a + b for a, b in zip(a_total, c[j][1:])]
            cost += c[j][0]
    for a in a_total:
        if a < x:
            break
    else:
        min_cost = min(cost, min_cost)

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

Submission status: Accepted

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

min = 10 ** 10
#ビット全探索
for i in range(2 ** n):
    #bag = []
    know = [0] * m
    total = 0
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            #bag.append(t[j][0])
            total += t[j][0]
            for k in range(m):
                know[k] += t[j][k+1]
    #print(bag)
    #print(know)
    for j in range(m):
        if know[j] < x:
            flag = False
            break
    #print(flag)
    if flag and total < min:
        min = total

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

Submission status: Accepted

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

ans = 10**7
for bit in range(2**n):
    alg = [0 for i in range(m)]
    ccount = 0
    for i in range(n):
        if bit >> i & 1:
            for j in range(m):
                alg[j] += a[i][j]
            ccount += cost[i]
    if min(alg) >= x:
        ans = min(ans,ccount)
if ans == 10**7:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,k,x = map(int,input().split())
ll = [list(map(int,input().split())) for _ in [0]*n]
costl = []
for i in range(2**n):
  fmt = '0'+str(n)+'b'
  s = format(i, fmt)
  suml = [0]*len(ll[0])
  for i in range(n):
    if s[i] == '1':
      for j in range(len(suml)):
        suml[j] += ll[i][j]
  if x<= min(suml[1:]):
    costl.append(suml[0])
print(min(costl) if len(costl)>0 else -1)

Submission status: Accepted

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

min_ans = 1e12
for i in range(int(pow(2, n))):
  idx = 1
  ans = []
  for j in range(n):
    if i & (idx << j) > 0:
      ans.append(j)
  aes = [0]*m
  c_sum = 0
  for j in ans:
    c_sum += c[j]
    for k in range(m):
      aes[k] += a[j][k]
  if not False in list(i >= x for i in aes):
    min_ans = min(min_ans, c_sum)

if min_ans == 1e12:
  print(-1)
else:
  print(min_ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
from itertools import product

CA = [
  list(map(int, input().split())) for _ in range(N)
]
P = list(product([0,1], repeat = N))

COST = 10 ** 9 + 7
for p in P:
  skill = [0]*M
  cost = 0
  for i, _p in enumerate(p):
    if _p == 0:
      cost += CA[i][0]
      for j in range(M):
        skill[j] += CA[i][j+1]
  #print(skill, cost)
  if min(skill) >= X:
    COST = min(COST, cost)

if COST == 10 ** 9 + 7:
  print(-1)
else:
  print(COST)

Submission status: Accepted

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

acq2 = 0
cost = []
skill = []
for i in range(n):
    ca = list(map(int, input().split()))
    cost.append(ca[0])
    skill.append(np.array(ca[1:]))

costmin = 0
for a in range(n):
    costmin += cost[a]

def tworaw(num):
    if (num % 2 == 0):
        return 0
    else:
        return 1

for j in range(2**n):
    buy = []
    cost_temp = 0
    skill_temp = np.zeros(m)
    acq = 1
    nn = j
    for k in range(n):
        buy.append(tworaw(nn))
        nn = nn // 2

    for l in range(n):
        if (buy[l] == 1):
            cost_temp += cost[l]
            skill_temp += skill[l]
    
    for b in range(m):
        if (skill_temp[b] < x):
            acq = 0
            break
    

    if (acq == 1):
        acq2 = 1
        if (cost_temp < costmin):
            costmin = cost_temp


if (acq2 == 1):
    print(int(costmin))
else:
    print('-1')

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
A=[list(map(int,input().split())) for _ in range (N)]
ans=10**20

for bit in range(2**N):
    C=[0]*M
    cost=0
    for i in range(N):
        if (bit>>i)&1==1:
            cost+=A[i][0]
            for j in range(1,M+1):
                C[j-1]+=A[i][j]
    if min(C)>=X:
        ans=min(ans,cost)
print(ans if ans!=10**20 else -1)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
C = []
A = []
for n in range(N):
    temp = [int(i) for i in input().split()]
    C.append(temp[0])
    A.append(temp[1:])
import numpy as np
np_A = np.array(A)
min_cost = 10**9
if np.all(np_A.sum(axis=0) >= X):
    for i in range(2**N):
        P = str(bin(i)).replace("0b","").zfill(N)
        score = np.zeros(M)
        cost = 0
        for j,p in enumerate(P):
            if p == "1":
                cost += C[j]
                score += np_A[j]
        if np.all(score >= X):
            min_cost = min(min_cost,cost)
    print(min_cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
C_li=[]
for _ in range(N):
    C=list(map(int,input().split()))
    C_li.append(C)
cost_min=10**9
for i in range(2**N):
    total=[0]*M
    cost=0
    for j in range(N):
        if (i>>j)&1:
            cost+=C_li[j][0]
            for k in range(M):
                total[k]+=C_li[j][k+1]
    flag=True
    for l in range(M):
        if total[l]<X:
            flag=False
    if flag==True and cost<cost_min:
        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())
x = [list(map(int, input().split())) for _ in range(N)]
ans = 10**20

for mask in range(2**N):
    C = [0]*M
    cst = 0
    for i in range(N):
        if (mask>>i)&1:
            cst += x[i][0]
            for j in range(1, M+1):
                C[j-1] += x[i][j]
    if min(C) >= X:
        ans = min(ans, cst)

if ans < 10**20:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

ans = 10**9
for bit in range(2**N):
    alg = [0]*M
    c = 0
    for i in range(N):
        if bit >> i & 1 == 1:
            for j in range(M):
                alg[j] += A[i][j]
            c += cost[i]
    if min(alg) >= X:
        ans = min(ans, c)

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

Submission status: Accepted

Solution code:
import numpy as np

n, m, x = map(int, input().split())
c = [None]*n
a = []
for i in range(n):
	tmp = list(map(int, input().split()))
	c[i] = tmp[0]
	a.append(np.array(tmp[1:]))

min_cost = float('inf')

for i in range(2**n):
	cost = 0
	skill = np.array([0]*m)
	for j in range(n):
		if i>>j & 1 == 1:
			cost += c[j]
			skill += a[j]
	
	if(np.all(skill >= x)):
		min_cost = min(cost, min_cost)

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

Submission status: Accepted

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

min_money = 999999999

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

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

	money = 0
	skill = [0] * m
	enough = [0] * m
	for sub in bag:
		money += sub[0]
		for k in range(1,m+1):
			skill[k-1] += sub[k]
			if skill[k-1] >= x:
				enough[k-1] = 1

	if 0 not in enough and min_money > money:
		min_money = money

if min_money != 999999999:
	print(min_money)
else:
	print(-1)

Submission status: Accepted

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

for i in range(2**n):
    lst_tent = [0 for i in range(m+1)]
    for j in range(n):
        if ((i >> j) & 1):
            for k in range(m+1):
                lst_tent[k] += lst[j][k]
    flag = 0
    for k in range(1,m+1):
        if lst_tent[k]<x:
            flag = 1
    if flag==0:
        ans = min(ans, lst_tent[0])

print(ans if ans!=float("INF") else -1)

Submission status: Accepted

Solution code:
import numpy as np 
from itertools import combinations

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

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

ans = []
for i in range(n):
    ptn = list(combinations(n_num, i+1))
    for j in range(len(ptn)):
        tmp = np.array([0]*(m+1))
        for k in range(len(ptn[j])):
            tmp += l[ptn[j][k]]
        if min(tmp[1:]) >= x:
            ans += [tmp[0]]

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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
S=[input().split() for _ in range(N)]
mintotal=10**9

for i in range(2**N):
    alg=[0]*M
    total=0
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(M):
                alg[k]+=int(S[j][k + 1])
            total+=int(S[j][0])

    for l in range(M):
        if alg[l] < X:
            break
    else:
      mintotal = min(mintotal,total)

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

Submission status: Accepted

Solution code:
from itertools import product

n, m, x = map(int, input().split())
ci = []
aij = []

for _ in range(n):
    c, *a = map(int, input().split())
    ci.append(c)
    aij.append(a)

min_used_money = float("inf")
for i in product([True, False], repeat=n):
    used_money = 0
    skills = [0] * m
    for j in range(n):
        if i[j]:
            used_money += ci[j]
            for k in range(m):
                skills[k] += aij[j][k]
    for k in range(m):
        if skills[k] < x:
            break
    else:
        min_used_money = min(min_used_money, used_money)

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

Submission status: Accepted

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

for i in range(N): 
    items = [int(v) for v in input().split()]
    books.append((items[0], items[1:]))

books = sorted(books)


def check(skill): 
    for item in skill: 
        if item < X:
            return False
    return True

queue = []

def buy_book(i, cost, input_skill):
    if i == N:
        if check(input_skill):
            queue.append(cost)
        return

    # 買わない
    buy_book (i+1, cost, input_skill)

    updated_cost = cost + books[i][0]
    updated_skill = [input_skill[i] for i in range(len(input_skill))] 
    for j in range(M): 
        updated_skill[j] = updated_skill[j] + books[i][1][j]
    buy_book (i+1, updated_cost, updated_skill)
 

buy_book(0, 0, [0 for i in range(M)])

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

Submission status: Accepted

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

n,m,k = map(int,input().split())
listA=[] #appendのために宣言が必要
while True:
    try:
        listA.append(list(map(int,input().split())))

    except:
        break;
        #または、quit(),os.exit()をして止める。
x=[[0] * (m+1) for i in range(2**n)] 
#print(listA)
for i in range(2 ** n):
    for j in range(n):
        if((i >> j) & 1 ):
            for l in range(m+1):
                x[i][l] += listA[j][l]
            
#print(x)
#print(list(range(1,m+1)))
cnt = 10**10
t = [k] * (m+1)
#print(t)
f = 0
for i in x:
    #print(i)
    u = 0
    for j in range(1, m+1):
        #print(1)
        if i[j] < t[j]:
            u = 1
    if u != 1:
        if cnt >= i[0]:
            cnt = i[0]
            f = 1
    #print(cnt)    
if f != 0:
    print(cnt)
else:
    print(-1)

Submission status: Accepted

Solution code:
def intlist(x):
    y = []
    for i in range(len(x)):
        y.append(int(x[i]))
    return y
 
N, M, X = map(int, input().split())
price = -1
 
L = []
a = []
c = []
suit =[]

for i in range(M+1):
    a.append(0)
    
for i in range(N):
    text = input().split()
    L.append(intlist(text))
    
for i in range(2**N):
    c = a.copy()
    
    for j in range(N):
        if (i >> j) & 1:
            for k in range(M+1):
                c[k] = c[k] + L[j][k]
    suit.append(c.copy())
                
suit2 = []

for i in range(len(suit)):
    if min(suit[i][1:len(suit)]) >= X:
        suit2.append(suit[i])
        


if suit2 != []:
    if len(suit2) >= 2:
    
        cheaper = suit2[0][0]
        for i in range(len(suit2)):
            if cheaper > suit2[i][0]:
                cheaper = suit2[i][0]
        price = cheaper
    elif len(suit2) == 1:
        price = suit2[0][0]
        
print(price)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
#N=参考書の冊数, 縦,M＝学びたいアルゴリズムの数, 横,X＝目標の理解度
S = [ input().split() for _ in range(N)]
mintotal = 10 ** 9

for i in range(2 ** N):
    alg = [0 for _ in range(M)]
    #bag = []
    total = 0
    #print("pattern {}:".format(i),  end="")
    for j in range(N):
        if ((i >> j) & 1):
            #bag.append(S[j])
            for k in range(M):
                alg[k] += int(S[j][k + 1])
            total += int(S[j][0])
    #print(alg, bag)

    for l in range(M):
        #print(alg[l])
        if alg[l] < X:
            break
    else:
        mintotal = min(mintotal, total)

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

Submission status: Accepted

Solution code:
# ABC167C

import numpy as np
import itertools

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

c = [0] * n
a = [0] * n
for i in range(n):
    temp = list(map(int, input().split()))
    c[i] = int(temp[0])
    a[i] = temp[1:]
a = np.array(a)
skill = a.sum(axis=0)
if np.all(skill >= x):
    bincombinations = list(itertools.product([0, 1], repeat = n))
    min_price = sum(c)
    for i, selection in enumerate(bincombinations):
        total_price = 0
        skill2 = np.zeros(m)
        for j in range(n):
            if selection[j] == 1:
                total_price += c[j]
                skill2 +=  a[j, :]
        if all(skill2 >= x):
            if total_price < min_price:
                min_price = total_price
    print(min_price)
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np 
from itertools import combinations

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

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

ptns = []
for i in range(n):
    ptns += list(combinations(n_num, i+1))

ans = float('inf')
for j in range(len(ptns)):
    tmp = np.array([0]*(m+1))
    for k in range(len(ptns[j])):
        tmp += l[ptns[j][k]]
    if min(tmp[1:]) >= x:
        ans = min(ans, tmp[0])
    
print(-1 if ans == float('inf') else ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
cm = []
llm = []
lf = []
for i in range(n):
    lm = [int(k) for k in input().split()]
    c = lm.pop(0)
    llm.append(lm)
    cm.append(c)
    lf.append(False)
mc = 10000000
fc = False
while True:
    #calc
    c = 0
    lx = [0 for j in range(m)]
    for i in range(n):
        if lf[i]:
            for j in range(m):
                lx[j] += llm[i][j]
            c += cm[i]
    fx = True
    for j in range(m):
        if lx[j] < x:
            fx = False
            break
    if fx:
        if mc > c:
            mc = c
            fc = True
    #next
    f = False
    for i in range(n):
        if f:
            break
        lf[i] = not lf[i]
        f = lf[i]
    if not f:
        break
if fc:
    print(mc)
else:
    print(-1)

Submission status: Accepted

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

a = [[0 for i in range(m)] for _ in range(n)]
c = [0] * n
for sankousyo in range(n):
    c_and_a = list(map(int,input().split()))
    c[sankousyo] = c_and_a[0]
    a[sankousyo] = c_and_a[1:]
    
cost = [0] * (2**n)
INF = 10**12
res_cost = INF
for i in range(2**n):
    understandings = [0] * m
    cost_sum = 0
    for j in range(n):
        if (i >> j) & 1:

            cost_sum += c[j]
            
            for k in range(m):
                understandings[k] = understandings[k] + a[j][k]

    res = True
    for j in range(m):
        if understandings[j] < x:
            res = False 

    if res:
        if res_cost > cost_sum:
            res_cost = cost_sum

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

Submission status: Accepted

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

l = list()

INF = float("inf")
ans = INF

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

for b in range(1, 1 << n):
	p = 0
	lm = [0] * m

	for j in range(n):
		if (b >> j) & 1:
			p += l[j][0]
			for k, v in enumerate(l[j][1]):
				lm[k] += v

	if min(lm) >= x:
		ans = min(ans, p)

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

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
money = [0] * N
A = [[0] * M for _ in range(N)]
for i in range(N):
    tmp = list(map(int, input().split()))
    money[i] = tmp[0]
    A[i] = tmp[1:]
# bit search
ans = 10**10
for i in range(2**(N)):
    books = []
    cost = 0
    for j in range(N):
        if i & (1 << j):
            books.append(j)
            cost += money[j]
    NowPower = [0] * M
    for b in books:
        for j in range(M):
            NowPower[j] += A[b][j]
    # check power
    flag = True
    for p in NowPower:
        if X > p:
            flag = False
    if flag:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for i in range(N)]
ans=float("inf")
for i in range(2**N):
    ruikei=[0]*M
    onedan=0
    for j in range(N):
        if ((i>>j)&1):
            onedan+=CA[j][0]
            for k in range(1,M+1):
                ruikei[k-1]+=CA[j][k]
    #print(onedan)
    #print(ruikei)    
    kari=True    
    for j in ruikei:
        if j<X:
            kari=False
    if kari:
        ans=min(ans,onedan)
if ans==float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[[0]*(m+1)]*n
for i in range(n):
    a[i]=list(map(int,input().split()))
b=[0]*(m+1)
flag=True
ans=-1
for i in range(2**n):
    flag=True
    b=[0]*(m+1)
    for j in range(n):
        if(i>>j & 1):
            for y in range(m+1):
                b[y]=b[y]+a[j][y]
    for y in range(1,m+1):
        if(b[y]<x):
            flag=False
            break
    if(flag):
        if ans<0 or b[0]<ans:
            ans=b[0]
print(ans)

Submission status: Accepted

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

price = sum(c)
l =0

for i in range(2**n):
    kari = 0
    skill = [0]*m
    for j in range(n):
        if (i>>j) & 1:
            skill = [x + y for(x,y) in zip(skill,a[j]) ]
            kari += c[j]
    if all([z >= x for z in skill]):
        price = min(price, kari)
        l += 1

if l == 0:
    print(-1)
else:
    print(price)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for i in range(N)]
ans=float("inf")
for i in range(2**N):
    ruikei=[0]*M
    onedan=0
    for j in range(N):
        if ((i>>j)&1):
            onedan+=CA[j][0]
            for k in range(1,M+1):
                ruikei[k-1]+=CA[j][k]
    #print(onedan)
    #print(ruikei)    
    kari=True    
    for j in ruikei:
        if j<X:
            kari=False
    if kari:
        ans=min(ans,onedan)
if ans==float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

books = {}
for i in range(N):
    hoge = list(map(int, input().split()))
    books[i] = hoge

Achievement = False

for n in range(2 ** N):
    conditions = [0 for m in range(M + 1)]  
    for i in range(N):
        if ((n >> i) & 1):
            for m in range(M + 1):
                conditions[m] += books[i][m]


    count = 0
    for m in range(1, M + 1):
        if conditions[m] < X:
            break
        count += 1
    if count == M:
        if Achievement == False:
            Achievement = True
            min = conditions[0]
        elif min > conditions[0]:
            min = conditions[0]

if Achievement == False:
    print(-1)
else:
    print(min)