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 = list(map(int,input().split()))

cList = []

for i in range(n):
    cList.append(list(map(int,input().split())))

priceList = []
for i in range(1,2**n):
    price = 0
    check = 1
    skilList = [0 for  i in range(m)]
    bit = i
    for j in range(1,n+1):
        if bit % 2 == 1:
            price += cList[j-1][0]
            for k in range(m):
                skilList[k] = skilList[k] + cList[j-1][k+1]
        bit = bit // 2
    for j in skilList:
        if j < x:
            check = 0
            break
    if check == 1:
        priceList.append(price)

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

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
value = []
books = []
for i in range(n):
    a = list(map(int,input().split()))
    value.append(a[0])
    books.append(np.array(a[1:]))
if min(sum(books))<x:
    print(-1)
else:
    ans = 10**8
    for i in range(2**n):
        M = np.array([0]*m)
        v = 0
        for j in range(n):
            if i >> j & 1:
                M += books[j]
                v += value[j]
        if min(M)>= x:
            ans = min(ans,v)
    print(ans)

Submission status: Accepted

Solution code:
INF = 10**8


def main():
    N, M, X = (int(i) for i in input().split())
    T = [[int(i) for i in input().split()] for j in range(N)]

    answer = INF
    for bit in range(1, 1 << N):
        intelligibility = [0]*M
        current_money = 0
        for i in range(N):
            if bit & 1 << i:
                current_money += T[i][0]
                for j, a in enumerate(T[i][1:]):
                    intelligibility[j] += a
        if all(X <= intelligence for intelligence in intelligibility):
            answer = min(answer, current_money)
    print(answer if answer != INF else -1)


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)]
ans = 100000000
for bit in range(1 << n):
    tmp_ca = [0] * (m+1)
    for j in range(n):
        if bit & (1 << j):
            for k in range(m+1):
                tmp_ca[k] += ca[j][k]
        tmp = 0
        for k in range(1,m+1):
            if tmp_ca[k] < x:
                tmp += 1
        if tmp == 0:
            ans = min(ans,tmp_ca[0])
if ans == 100000000:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import bisect
N, M, X = map(int, input().split())
C = [0] * N
A = [0] * N
for i in range(N):
    x = list(map(int, input().split()))
    C[i] = x[0]
    A[i] = [0] * M
    for j in range(M):
        A[i][j] = x[j + 1]
cnt = [0] * (2 ** N)
ans_list = []
for i in range(2 ** N):
    bag = []
    cnt[i] = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            bag.append(C[j])
            for k in range(M):
                cnt[i][k] += A[j][k]
    cnt[i].sort()
    if bisect.bisect_left(cnt[i], X) == 0:
        ans_list.append(sum(bag))
if ans_list == []:
    print(-1)
else:
    print(min(ans_list))

Submission status: Accepted

Solution code:
import numpy as np

def list_element_add(l1, l2):
    result = np.array(l1) + np.array(l2)
    return result.tolist()

def solve(l, ave):
    for k in l:
        if k < ave:
            return False
    else:
        return True

n,m,x = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(n)]
ans = 10**12

for i in range(2**n):
    understanding = [0]*m
    money = 0
    for j in range(n):
        if ((i >> j) & 1):
            money += c[j][0]
            understanding = list_element_add(understanding, c[j][1::])
    if solve(understanding, x):
        ans = min(ans,money)

print(ans if ans != 10**12 else '-1')

Submission status: Accepted

Solution code:
import copy
 
N,M,X = map(int,input().split())
 
res = 10**8
 
C = [0] * N
A = [0] * N
 
for i in range(N):
    L = list(map(int,input().split()))
    C[i] = L[0]
    A[i] = L[1:]
 
def check_x(a):
    for i in range(len(a)):
        if a[i] < X:
            return False
    return True
 
# n…2^12(12bit)の整数
def calc_money_under(n):
    global res

    understand = [0] * M
    money = 0
    for s in range(N):
        if (n >> s) & 1:
            money += C[s]
            for j in range(M):
                understand[j] += A[s][j]
            #print(understand)
    
    if check_x(understand):
        res = min(money, res)
    return
 
for n in range(2**N):
    calc_money_under(n)
 
if res == 10**8:
    print(-1)
else:
    print(res)

Submission status: Accepted

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

ans=sum(C)+1
for seq in itertools.product(range(2),repeat=N):
    R=[0 for i in range(M)]
    cost=0
    for i in range(N):
        if seq[i]==0:
            continue
        cost+=C[i]
        for j in range(M):
            R[j]+=A[i][j]
    if min(R)>=X:
        ans=min(ans,cost)
if ans==sum(C)+1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

A = [list(map(int, input().split())) for j in range(n)]
ans = 10 ** 7
for i in range(1 << n):
    s = [0] * (m + 1)
    for j in range(n):
        if i >> j & 1:
            for k in range(m+1):
                s[k] += A[j][k]
    if min(s[1:]) >= x:
        ans = min(ans, s[0])
print(-1) if ans == 10 ** 7 else print(ans)

Submission status: Accepted

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

price = []
ability = []
for _ in range(n):
  lst = []
  lst = [int(i) for i in input().split()]
  price.append(lst[0])
  ability.append(lst[1:m + 1])
#print(price)
#print(ability)
min_price = float('inf')
for i in range(2 ** n):
  flag = True
  total = 0
  obtain = [0] * m
  for j in range(n):
    if ((i >> j) & 1):
      total += price[j]
      for k in range(m):
        obtain[k] += ability[j][k]
  for j in range(m):
    if obtain[j] < x:
      flag = False
      break
  if flag:
    if total < min_price:
      min_price = total
if min_price == float('inf'):
  print(-1)
else:
  print(min_price)

Submission status: Accepted

Solution code:
import itertools

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

ans = float('inf')

for p in itertools.product(range(2), repeat=n):
    knowledges = [0 for _ in range(m)]
    tmp = 0

    for i,a in zip(p,A):
        if i == 0: continue
        tmp += a[0]
        for j,anm in enumerate(a[1:]): knowledges[j] += anm
    
    if all([a >= x for a in knowledges]):
        ans = min(ans, tmp)

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

Submission status: Accepted

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


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

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

  min_ = float('inf')
  for bit in range(1 << N):
    temp = [0]*M
    cost = 0
    for i in range(N):
      mask = 1 << i
      if bit & mask:
        cost += C[i]
        for j, a in enumerate(A[i]):
          temp[j] += a

    if all(list(map(lambda x: x >= X, temp))):
      min_ = min(min_, cost)

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


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
c=[list(map(int,input().split())) for _ in range(n)]
import itertools
sum_min=10**7
for i in itertools.product([0,1],repeat=n):
    level=[0]*m
    for j in range(m):
        level[j]=sum(i[k]*c[k][j+1] for k in range(n))
    for l in range(m):
        if level[l]<x:
            break
    else:
        sum_min=min(sum_min,sum(i[k]*c[k][0] for k in range(n)))
print(sum_min if sum_min!=10**7 else -1)

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
ans=[]
for i in range(2**N):
    cost=0
    m=[0]*M
    for j in range(N):
        if ((i>>j)&1):
            cost+=A[j][0]
            for k in range(M):
                m[k]+=A[j][k+1]
    m7=[l for l in m if X<=l]
    if len(m7)==M:
        ans.append(cost)
if len(ans)>0:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = []
A = []
ans = float("inf")
for _ in range(n):
    tmp = list(map(int, input().split()))
    C.append(tmp[0])
    A.append(tmp[1:])

for i in range(2**n):
    now = [0] * m
    ns = 0

    for j in range(n):
        if i&(1<<j):
            ns += C[j]

            for k in range(m):
                now[k] += A[j][k]

    if min(now) >= x:
        ans = min(ans, ns)

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

Submission status: Accepted

Solution code:
n,m,l = map(int,input().split())
c = [list(map(int,input().split())) for i in range(n)]
p = 'a'
for i in range(2**n):
    x = i
    y = [0] * m
    z = 0
    for j in range(n):
        if x % 2 != 0:
            z += c[j][0]
            for k in range(m):
                y[k] += c[j][k+1]
        x = x // 2
    if min(y) >= l:
        if p != 'a':
            p = min(p,z)
        else:
            p = z
if p != 'a':
    print(p)
else:
    print(-1)

Submission status: Accepted

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

min_num = 10**18

for i in range(1<<n):
    cost = 0
    l = [0]*m
    for j in range(n):
        if (i>>j)&1:
            c, *a = book[j]
            cost += c
            for k ,ak in enumerate(a):
                l[k] += ak
    if all(lj >= x for lj in l):
        min_num = min(min_num,cost)

print(-1 if min_num == 10**18 else min_num)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = []
A = []
ans = float("inf")
for _ in range(n):
    tmp = list(map(int, input().split()))
    C.append(tmp[0])
    A.append(tmp[1:])

for i in range(2**n):
    now = [0] * m
    ns = 0

    for j in range(n):
        if i&(2**j):
            ns += C[j]

            for k in range(m):
                now[k] += A[j][k]

    if min(now) >= x:
        ans = min(ans, ns)

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

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])
    A.append(t[1:])

result = -1
# 1 << N 2^N
#There are 2^N possible ways of choosing books
for i in range(1 << N):
    #keep all the understanding level in u
    u = [0]*M
    c = 0
    for j in range(N):
        #move j bit from i
        if (i>>j)&1 == 0:
            continue
        c+= C[j]
        #listwise sum
        for k in range(M):
            u[k] += A[j][k]
        #X is the desired understanding level    
    if all(x >= X for x in u):
        if result == -1:
            result = c
        else:
            result = min(result,c)
            
print(result)

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement, product
import numpy as np
def input(): return sys.stdin.readline().rstrip()


def main():
    n, m, x = map(int, input().split())
    data = np.zeros((n,m+1),int)
    ans=10**10
    for i in range(n):
        data[i]=np.array(list(map(int, input().split())))
    for bit in list(product([0,1],repeat=n)):
        calc=np.dot(np.array(bit), data)
        if all(calc[1:]>=x):
            ans=min(ans,calc[0])
    
    if ans==10**10:
        print(-1)
    else:
        print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations_with_replacement, product
import numpy as np
def input(): return sys.stdin.readline().rstrip()

def main():
    n, m, x = map(int, input().split())
    data = np.zeros((n,m),int)
    clist = np.zeros(n, int)
    ans=10**10
    for i in range(n):
        ca = list(map(int, input().split()))
        clist[i]=ca[0]
        data[i]=np.array(ca[1:])
    for bit in list(product([0,1],repeat=n)):
        if all(np.dot(np.array(bit), data)>=x):
            ans=min(ans,np.dot(np.array(bit),clist.T))
    
    if ans==10**10:
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n,m,x=map(int,input().split())
ac=[[0]*(m+1) for i in range(n)]
a=[[0]*m for i in range(0,n)]
c=[0 for i in range(n)]
for i in range(n):
  ac[i]=list(map(int,input().split()))
  c[i]=ac[i][0]
  a[i]=ac[i][1:m+1]#sliceは上限+１を:の右に代入
cheap=[]
kaukadouka=[0 for i in range(n)]

def kau(i):
  global a,x,kaukadouka,cheap,c
  rikaido=[0 for i in range(m)]#初期化
  for j in range(i+1,n):
    kaukadouka[j]=0
  if i>=n:
      sys.exit()
  kaukadouka[i]=1
  for j in range(n):
    for k in range(m):
      rikaido[k]+=kaukadouka[j]*a[j][k]
  value=0
  if min(rikaido)>=x:
    for j in range(n):
      value+=c[j]*kaukadouka[j]
    cheap.append(value)
  if i<n-1:
    kau(i+1)
    kawanai(i+1)
    
def kawanai(i):
  global kaukadouka
  for j in range(i,n):
    kaukadouka[j]=0

  if i>=n:
    sys.exit()
  #print('i=',i,'のとき買わないで')
  #print('->',kaukadouka)

  if i<n-1:
    kau(i+1)
    kawanai(i+1)

kau(0)
kawanai(0)
if len(cheap)>0:
	#print(cheap)
	print(min(cheap))
else:
  print('-1')

Submission status: Accepted

Solution code:
from itertools import combinations
n,m,x = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(n)]

ans = float("inf")
for i in range(1,n+1):
  for j in combinations(ca,i):
    l = [0]*(m+1)
    for k in j:
      for i2 in range(m+1):
        l[i2] += k[i2]
    if all(l[num] >= x for num in range(1,m+1)):
      ans = min(ans, l[0])
if ans == float("inf"): print(-1)
else: print(ans)

Submission status: Accepted

Solution code:
import math

n, m, x = map(int, input().split())
books = []
for i in range(n):
    books.append(list(map(int, input().split())))
n_bin = '1'*n
_n = (int(n_bin, 2))+1
ans = 10**9

for i in range(_n):
    target = bin(i).replace('0b', '').zfill(n)
    tmp_skill = [0 for i in range(len(books[0])-1)]
    tmp_price = 0
    
    for j in range(len(target)):
        if target[j] == '1':
            tmp_price += books[j][0]
            for k in range(len(tmp_skill)):
                tmp_skill[k] += books[j][k+1]
        for k in range(len(tmp_skill)):
            if tmp_skill[k] < x:
                break
        else:
            ans = min(ans, tmp_price)
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product

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

C, A = [], []
for i in range(N):
    C.append(inp[i][0])
    A.append(inp[i][1:])

#判定
z_A = list(zip(*A))
for i in range(M):
    if sum(z_A[i]) < X:
        print(-1)
        exit()

ans = sum(C)

for buy_bit in product(range(2), repeat=N):
    buy = 0
    tmp = 0
    skill = [0] * M
    for i in range(N):
        if buy_bit[i]:
            for j in range(M):
                skill[j] += A[i][j]
            buy += C[i]
    
    f = True
    for s in skill:
        if s < X:
            f = False
            break
    if f:
        ans = min(ans, buy)

print(ans)

Submission status: Accepted

Solution code:
#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

n,m,x=input2()
CA=[]
ans=10**9

for _ in range(n):
	CA.append(input_array())

# ビット全探索
for i in range(2**n):
	bag=[]
	for j in range(n): #ビット全探索
		if (i>>j) & 1:
			bag.append(CA[j])
	enoughs=[0]*m #スキルがx以上身に付く数
	skills=[0]*m #身に付くスキルの合計
	money=0 #探索中の金額

	for b in bag:
		money+=b[0]
		for k in range(1,m+1):
			skills[k-1]+=b[k]
			if skills[k-1]>=x:
				enoughs[k-1]+=1
	if 0 not in enoughs: #スキルが充足
		if money<ans:
			ans=money #価格の更新
if ans==10**9:
	print(-1)
else:
	print(ans)

Submission status: Accepted

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

min_num = 10**18
for i in range(1<<N):
    cost = 0
    l = [0]*M
    for j in range(N):
        if (i>>j)&1:
            c, *a = CA[j]
            cost += c
            for k, ak in enumerate(a):
                l[k] += ak
    if all(lj >= X for lj in l):
        min_num = min(min_num, cost)
    # print(l)

print(-1 if min_num == 10**18 else min_num)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
dat = []
gold = []
for i in range(n):
    l = list(map(int, input().split()))
    gold.append(l[0])
    dat.append(l[1:])
inf = 99999999999999999999
minval = inf
for pat in range(2 ** n):
    tmp = [0] * m
    cost = 0
    for i in range(n):
        if (pat >> i & 1) == 1:
            cost += gold[i]
            for j in range(m):
                tmp[j] += dat[i][j]
    can = True
    for i in range(m):
        if tmp[i] < x:
            can = False
            break
    if can is False:
        continue
    minval = min(minval, cost)

if minval == inf:
    print(-1)
else:
    print(minval)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N,M,X=map(int, sys.stdin.readline().split())
CA=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

ans=float("inf")

for n in range(2**N):
    #先頭列が金額、後は各アルゴリズムの理解度の合計値
    L=[ 0 for _ in range(M+1) ]
    for keta in range(N):
        if n%2==1:
            for i,t in enumerate(CA[keta]):
                L[i]+=t
        n/=2
        if X<=min(L[1:]):
            ans=min(ans,L[0])

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
c=[]
a=[]
mn=float("inf")
for i in range(n):
  aa=list(map(int,input().split()))
  c.append(aa.pop(0))
  a.append(aa)

for i in range(2**n):
  buy=[]
  kai=[0]*m
  cost=0
  for j in range(n):
    if((i>>j)&1):
      buy.append(j)
  for j in buy:
    cost+=c[j]
    for k in range(m):
      kai[k]+=a[j][k]
  fl=True
  for j in range(m):
    if kai[j]<x:
      fl=False
      break
  if fl:
    mn=min(mn,cost)
if mn==float("inf"):
  print(-1)
else:
  print(mn)

Submission status: Accepted

Solution code:
def get_items(arr,idx_arr):
    return [arr[i] for i in range(len(arr)) if i in idx_arr]

def to_binaly_arr(val,digit_num):
    return list(bin(val)[2:].zfill(digit_num))

def get_one_idx(binaly_arr):
    return [idx for idx in range(len(binaly_arr)) if binaly_arr[idx] == "1"]

def get_arr_sum(mat):
    if len(mat) == 0:
        return []
    else:
        sum_arr = []
        for j in range(len(mat[0])):
            sum_val = 0
            for i in range(len(mat)):
                sum_val += mat[i][j]
            sum_arr.append(sum_val)
        return sum_arr
def is_all_item_over_X(arr,X):
    return (not (False in [item>=X for item in arr])) and len(arr) > 0

if __name__ == "__main__":
    N,M,X = map(int,input().split())
    C,A = [],[]
    for i in range(N):
        input_val = list(map(int,input().split()))
        C.append(input_val[0])
        A.append(input_val[1:])
    min_price = float("inf")
    for i in range(0,2**N):
        idx_arr = get_one_idx(to_binaly_arr(i,N))
        arr_sum = (get_arr_sum(get_items(A,idx_arr)))
        if is_all_item_over_X(arr_sum,X) == True:
            min_price = min(min_price,sum(get_items(C,idx_arr)))
    if min_price == float("inf"):
        print(-1)
    else:
        print(min_price)

Submission status: Accepted

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

for i in range(2**N):
    flag = 0
    c = 0
    total = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            c += C[j]
            for k in range(M):
                total[k] += A[j][k]
    for k in range(M):
        if total[k] < X:
            flag = 1
            break
    if flag == 1:
        continue
    anslist.append(c)

if len(anslist) != 0:
    anslist.sort()
    ans = anslist[0]

print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [0] * n
a = [0] * n
for i in range(n):
    c[i], *a[i] = list(map(int, input().split()))
ans = 10 ** 9
for i in range(2 ** n):
    csum = 0
    asum = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            csum += c[j]
            for k in range(m):
                asum[k] += a[j][k]
    if len(list(filter(lambda v: v >= x, asum))) == m:
        ans = min(ans, csum)
print(-1 if ans == 10 ** 9 else ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys, math

n,m,x = [int(x) for x in stdin.readline().rstrip().split()]

c = []
for i in range(n):
    c.append([int(x) for x in stdin.readline().rstrip().split()])

money = []
for i in range(2**n):
    b = bin(i)
    d = [0 for i in range(m + 1)]
    for j in range(n):
        if b[-1] == "1": d = [p+q for (p,q) in zip(d,c[j])]
        b = str(bin(int(b, 2) // 2))

    if min(d[1:]) >= x: money.append(d[0])

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

Submission status: Accepted

Solution code:
import itertools

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

c = [ (0, 1) for _ in range(n)]
min_price = float('inf')

for cc in itertools.product(*c):
  xx = [0] * m
  price = 0
  for i, ccc in enumerate(cc):
    if ccc==1:
      price += A[i][0]
      xx = [a +b for a, b in zip(xx, A[i][1:])]
  if min(xx) >= x:
    min_price = min(min_price, price)

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

Submission status: Accepted

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

answer=0
answerlist=[]
for i in range(2**N):
  brain=[0]*M
  answer=0
  for j in range(N):
    if ((i>>j)&1):
      answer+=int(query[j][0])
      for l in range(M):
        brain[l]+=int(query[j][l+1])
  if (all([i>=X for i in brain])):
      answerlist.append(answer)
if answerlist==[]:
  print(-1)
else:
  print(min(answerlist))

Submission status: Accepted

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

a = [[0] * m for j in range(n)]
c = [0] * n

ans = 10**10

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

# bit全探索
import itertools
for bit in itertools.product([0,1], repeat=n):
    arr = [0] * m
    cost = 0
    for i in range(n):
        if bit[i] == 1:
            for k in range(len(a[i])):
                arr[k] += a[i][k]
            cost += c[i]

    NG = False
    for i in range(len(arr)):
        if arr[i] < x:
            NG = True
            
    if NG:
        pass
    else:
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
number=list(map(int,input().split()))
n,m,x=number[0],number[1],number[2]
books=[list(map(int,input().split())) for i in range(n)]
U=[x for i in range(m+1)]
U[0]=0
pattern=[]
answer=[]


for i in range(2**n):
    tmp=[False]*n
    for j in range(n):
        if (i>>j)&1:
            tmp[j]=True
    
    pattern.append(tmp)

for i in range(2**n):
    cost=0
    U=[x for i in range(m+1)]
    U[0]=0
    for j in range(n):
        if pattern[i][j]==True:
            cost+=books[j][0]
            for k in range(1,m+1):
                U[k]-=books[j][k]
                if max(U)==0:
                    answer.append(cost)
                    break
                    
if answer==[]:
    print(-1)
else:
    print(min(answer))

Submission status: Accepted

Solution code:
import itertools

dd = list(map(int,input().split()))
NN = dd[0]
MM = dd[1]
XX = dd[2]
success = 0
min_price = 100000*13
arr = [list(map(int,input().split())) for i in range(NN)]
for i in range(1,NN+1):
    comb = list(itertools.combinations(arr,i))
    for j in range(len(comb)):
        total_price = 0
        total_skill = [0]*MM
        doable = [0]*MM
        for k in range(i):
            total_price = total_price + comb[j][k][0]
            for l in range(MM):
                total_skill[l] = total_skill[l] + comb[j][k][l+1]
                if total_skill[l] >= XX:
                    doable[l] = 1
        if min(doable) == 1:
            success = 1
            if total_price < min_price:
                min_price = total_price
if success == 0:
    print(-1)
else:
    print(min_price)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
c = [0] * n
a = [0] * n
for i in range(n):
    xs = list(map(int, input().split()))
    c[i] = xs[0]
    a[i] = xs[1:]
ans = 10 ** 9
for i in range(2 ** n):
    csum = 0
    asum = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            csum += c[j]
            for k in range(m):
                asum[k] += a[j][k]
    if len(list(filter(lambda v: v >= x, asum))) == m:
        ans = min(ans, csum)
print(-1 if ans == 10 ** 9 else ans)

Submission status: Accepted

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

ans = 10**9
for i in range(1 << n):
    money = 0
    ex = [0]*m
    for j in range(n):
        if (i >> j) & 1 == 0: continue
        money += a[j]
        for k in range(m):
            ex[k] += b[j][k]
    if all(x <= l for l in ex):
        ans = min(ans,money)
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

INF = 10**18
ans = INF
for mask in range(1<<N):
    skill = [0 for i in range(M)]
    cost = 0
    for i in range(N):
        if mask&(1<<i):
            cost += C[i]
            for j in range(M):
                skill[j] += A[i][j]
    if min(skill) >= X:
        ans = min(ans,cost)
print(-1 if ans==INF else ans)

Submission status: Accepted

Solution code:
import itertools
n,m,x=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(n)]
ans=10**7
for buy in itertools.product(range(2),repeat=n):
  judge=[0]*(m+1)
  for i in range(n):
    if buy[i]==1:
      for j in range(m+1):
        judge[j]+=lst[i][j]
  jd=True
  for i in range(1,m+1):
    if judge[i]<x:
      jd=False
      break
  if jd:
    ans=min(ans,judge[0])
if ans==10**7:
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
import math
n,m,x = map(int,input().split())
book = [list(map(int,input().split())) for _ in range(n)]
best = math.inf

for i in range(2**n):
    und = [0]*m
    money = 0
    for j in range(n):
        if (i>>j) & 1:
            money += book[j][0]
            for k in range(m):
                und[k] += book[j][k+1]
    if all(s>=x for s in und) and best>money:
        best = money

if best==math.inf:
    print(-1)
else:
    print(best)

Submission status: Accepted

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

ans = -1
for i in range(2**N):
    c = 0
    R = [0 for _ in range(M)]
    for j in range(N):
        if (i>>j) % 2:
            c += C[j]
            for m in range(M):
                R[m] += A[j][m]
    flag = True
    for m in range(M):
        if R[m] < X:
            flag = False
            break
    if flag:
        if ans == -1:
            ans = c
        elif ans > c:
            ans = c

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')
from itertools import combinations as com
for l in range(1,n+1):
    for i in com(list(range(n)),r=l):
        cnt=[0]*m
        p=0
        for j in i:
            p+=c[j][0]
            for x in range(m):
                cnt[x]+=c[j][x+1]
        if min(cnt)>=X:ans=min(ans,p)
print(ans if ans!=float('inf')else -1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
books = [list(map(int, input().split())) for _ in range(n)]
INF = 10 ** 9 + 7

ans = INF
for bits in range(2 ** n):
    cost = 0
    score = [0] * m
    for i, book in enumerate(books):
        if bits >> i & 1:
            cost += book[0]
            score = [s + b for s, b in zip(score, book[1:])]
    if all(s >= x for s in score):
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
money=[]
skill=[]
for i in range(n):
  a=list(map(int,input().split()))
  money+=[a[0]]
  skill+=[a[1:m+1]]
ans=-1
for i in range(2**n):
  total=0
  learn=[0]*m
  for j in range(n):
    if (i>>j)&1:
      total+=money[j]
      for a in range(m):
        learn[a]+=skill[j][a]
  if len([i for i in learn if i>=x])==m:
    if ans==-1:
      ans=total
    elif ans>total:
      ans=total
print(ans)