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:
class solver :
	def __init__(self) :
		self.n, self.m, self.x = map(int, input().split())
		self.initVariables()
		for i in range(self.n) :
			self.a[i] = [int(i) for i in input().split()]

	def initVariables(self) :
		self.a = [list() for i in range(self.n)]

	def checkRequirement(self, skill) :
		for i in skill :
			if i < self.x :
				return False
		return True

	def getResult(self, mask) :
		skill = [0] * self.m
		cost = 0
		for i in range(self.n) :
			if mask % 2 == 1:
				cost += self.a[i][0]
				for j in range(self.m) :
					skill[j] += self.a[i][j + 1] 
			mask //= 2
		return (cost, self.checkRequirement(skill))

	def solve(self) :
		ans = [-1, False]
		for mask in range(2 ** self.n) :
			cur = self.getResult(mask)
			if cur[1] == True :
				if ans[1] == False or cur[0] < ans[0] :
					ans = cur
		return ans

print(solver().solve()[0])

Submission status: Accepted

Solution code:
import itertools
from sys import stdin


def get_result(data):
    N, M, X = data[0]
    C_A = data[1:]
    min_const = float('inf')
    for bit in itertools.product([0, 1], repeat=N):
        cost = 0
        comp = [0] * M
        for i, val in enumerate(bit):
            if val == 1:
                cost += C_A[i][0]
                for j in range(M):
                    comp[j] += C_A[i][j+1]

        if min(comp) >= X and cost < min_const:
            min_const = cost

    return -1 if min_const == float('inf') else min_const


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

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))
 
def buy(x,y):
    
    if x + y <= N:
        
        for i in range(0,M+1):
            
            a[i] += L[x+y-1][i]
            
       
        if x + y == N:
            score = a[1:len(a)]
            
            if min(score) >= X:
                suit.append(a.copy())
                
        elif x + y != N:
            buy(x+1,y)
            for i in range(0,M+1):
                a[i] -= L[x+y][i]
           
            notbuy(x,y+1)
 
 
def notbuy(x,y):
   
    if x + y <= N:
        
        if x + y == N:
            score = a[1:len(a)]
            if min(score) >= X:
                suit.append(a.copy())
                    
             
        elif x + y != N:
            buy(x+1,y)
            for i in range(0,M+1):
                a[i] -= L[x+y][i]
            notbuy(x,y+1)    
 
def textbook(x,y):
    buy(x+1,y)
    for i in range(0,M+1):
        a[i] -= L[x+y][i]
    notbuy(x,y+1)
 
textbook(0,0)
 



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


print(price)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
ca = [[int(i) for i in input().split()] for j in range(n)]
stack = [0 for i in range(n)]
cmin = 12345678
while not stack==[]:
    s = [0 for i in range(m+1)]
    for i in range(n):
        if stack[i]==1:
            for j in range(m+1):
                s[j] += ca[i][j]
    if s[0]<cmin:
        xok = True
        for i in range(1,m+1):
            if s[i]<x:
                xok = False
        if xok:
            cmin = s[0]
    for i in range(n):
        p = stack.pop()
        if p == 0:
            stack.append(1)
            for j in range(i):
                stack.append(0)
            break
        
if cmin==12345678:
    print(-1)
else:
    print(cmin)

Submission status: Accepted

Solution code:
import numpy as np

n,m,x=map(int,input().split(' '))
text=[0]*n
for i in range(n):
    text[i]=np.array(list(map(int,input().split(' '))))

money=float('inf')
    
for i in range(2**n):
    buy=np.zeros(m+1)
    for j in range(n):
        if (i>>j) & 1:
            buy += text[j]
        if buy[1:].min() >=x:
            if buy[0] < money:
                money = buy[0]
                
if money == float('inf'):
    print(-1)
else:
    print(int(money))

Submission status: Accepted

Solution code:
import math

def resolve():
    N, M, X = map(int, input().split())
    C_list = []
    A_list = []

    for i in range(N):
        tmp_list = list(map(int, input().split()))
        C_list.append(tmp_list.pop(0))
        A_list.append(tmp_list)
    
    ans = math.inf
    for b in range(1 << N):
        cost = 0
        d_list = [0 for i in range(M)]
        for i in range(N):
            if b >> i & 1:
                cost += C_list[i]
                for j in range(M):
                    d_list[j] += A_list[i][j]

        flag = True
        for d in d_list:
            if d < X:
                flag = False
        if flag:
            ans = min(ans, cost)
    
    if ans == math.inf:
        print(-1)
    else:
        print(ans)

    return
        

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import numpy as np

N, M, X = map(int, input().split())
C = np.zeros(N)
A = np.zeros((N, M))


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

C_MIN = -1
for i in range(2 ** N):
    C_SUM = 0
    A_SUM = np.zeros(M)
    for j in range(N):
        if ((i >> j) & 1):
            C_SUM += C[j]
            A_SUM += A[j]
    if np.all(A_SUM >= X):
        if C_SUM < C_MIN or C_MIN == -1:
            C_MIN = C_SUM
            
if C_MIN == -1:
    print("-1")
else:
    print(int(C_MIN))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def main() -> None:
    N, M, X = rmi()
    C, A = [], []
    for n in range(N):
        args = rmi()
        C.append(args[0])
        A.append(args[1:])
    possible = False
    cost = sum(C)
    from itertools import product
    for bitset in product((True, False), repeat=N):
        test = [0] * M
        for n in range(N):
            if bitset[n]:
                test = [t + a for (t, a) in zip(test, A[n])]
        current_cost = sum([c for i, c in enumerate(C) if bitset[i]])
        if X <= min(test):
            cost = min(cost, current_cost)
            possible = True
    w(cost if possible else -1)


def int2bit(decimal: int, digits: int = 0) -> str:
    if digits <= 0:
        return '{:b}'.format(decimal)
    else:
        return ('{:' + str(digits) + 'b}').format(decimal)


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10 ** 9)
    main()

Submission status: Accepted

Solution code:
import numpy as np
def func(ans, b_list, a_list, c_list, k, x):
    if k == 0:
        b_list = np.asarray(b_list)
        x_list = np.dot(b_list, a_list)
        if np.all(x_list >= x):
            return np.inner(c_list, b_list)
        else:
            return ans
    ans = min(ans, func(ans, b_list + [1], a_list, c_list, k - 1, x))
    ans = min(ans, func(ans, b_list + [0], a_list, c_list, k - 1, x))
    return ans
n, m, x = map(int, input().split())
c_list = [] 
a_list = []
for i in range(0, n):
    c, *a = map(int, input().split())
    c_list.append(c)
    a_list.append(a)
ans = float("inf")
c_list = np.asarray(c_list)
a_list = np.asarray(a_list)
ans = min(ans, func(ans, [1], a_list, c_list, n - 1, x))
ans = min(ans, func(ans, [0], a_list, c_list, n - 1, x))
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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


for i in range(2**N):
    score = [0 for _ in range(M)]
    price = 0
    for j in range(N):
        if i & 1<<j:
            for k in range(M):
                score[k] += A[j][k]
            price += C[j]    
    if min(score) >= X:
        if min_price == -1 or min_price > price:
            min_price = price

print(min_price)

Submission status: Accepted

Solution code:
from itertools import product
from operator import add

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

p = list(product([0, 1], repeat=n))
ans = float('inf')
for i in range(len(p)):
    total = [0]*m
    money = 0
    for j in range(n):
        if p[i][j] == 1:
            total = list(map(add, total, ca[j][1:m+1]))
            money += ca[j][0]
    if len([y for y in total if y >= x]) == m:
        ans = min(ans, money)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
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:])
  #print(n, m, x)
  #print(c)
  #print(a)
  
  def check(b):
    p = b
    y = [0]*m
    z = 0
    for i in range(n):
      if p % 2 == 1:
        #print(i, end=",")
        for j in range(m):
          y[j] += a[i][j]
        z += c[i]
      p = p >> 1
    #print("value =", z)
    for j in range(m):
      if y[j] < x:
        return False, -1
    return True, z
      
  minx = None
  for b in range(2**n):
    #print(b)
    flg, val = check(b)
    if flg:
      minx = val if minx is None else min(val, minx) 
  print(-1 if minx is None else minx)
main()

Submission status: Accepted

Solution code:
def dfs(i, cost, skill):
    if i == n:
        if min(skill) >= x:
            return cost
        else:
            return INF
    updated_skill = [0] * m
    updated_cost = cost + C[i]
    for j in range(m):
        updated_skill[j] = skill[j] + A[i][j]
    return min(dfs(i + 1, cost, skill), dfs(i + 1, updated_cost, updated_skill))
    # return dfs(i + 1, updated_cost, updated_skill)
    # return dfs(i + 1, cost, skill)

    # skill1 = A[1][0] + A[2][0] + A[3][0]
    # skill2 = A[1][1] + A[2][1] + A[3][1]


    # return xxxxxxxxxxxxx


INF = float('inf')

n, m, x = map(int, input().split())
C = []
A = []

# n = 3
# m = 3
# x = 10
# C = [60, 70, 50]
# A = [
#     [2, 2, 4], [8, 7, 9], [2, 3, 9]
# ]

for _ in range(n):
    li = list(map(int, input().split()))
    C.append(li[0])
    A.append(li[1:])
# print(C)
# print(A)

min_cost = dfs(0, 0, [0] * m)
if min_cost == INF:
    print('-1')
else:
    print(min_cost)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
C = []
A = []
for i in range(n):
    L = list(map(int, input().split()))
    C.append(L[0])
    A.append(L[1:m+1])
# print(C, A)
ans = sum(C) + 1

for i in range(2**n):
    # print(bin(i))
    study = [0] * m
    price = 0
    for j in range(n):
        if i >> j & 1:
            for k in range(m):
                study[k] += A[j][k]
            price += C[j]
            # print(study, price)
            if min(study) >= x:
                ans = min(ans, price)

if ans == sum(C) + 1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def ha(mm,x):
    mm=[1  if i//x >=1 else 0 for i in mm]
    if sum(mm)>=len(mm):
        return 0
    else:
        return 1

def so(hr,ca,m,an):
    wk = 0
    mm = [0]*m
    for i in range(len(hr)):
        if hr[i] == 1:
            wk += ca[i][0]
            hr[i] = 1
            for j in range(m):
                mm[j] += ca[i][j+1]
        else:
            i += 1
    if ha(mm,x)==0:
        an=min(wk,an)
        return an
    return an

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

ca=[]
an = 0
for i in range(n):
    ca.append(list(map(int,input().split())))
    an += ca[i][0]

an += 1
han = an
hr = [0]*n
for ka in range(1,2**n):
    hr = [int(i) for i in list(format(ka, 'b').zfill(n))]
    an = so(hr,ca,m,an)
if an == han:
    print('-1')
else:
    print(an)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
INF = 10000000
def main():
    N, M, X = map(int, input().split())
    book = []
    ans = INF
    for i in range(N):
        info = [int(i) for i in input().split()]
        book.append(info)
    for i in range(1 << N):
        a = []
        for j in range(M + 1):
            a.append(0)    
        for j in range(N):
            if (i >> j) & 1:
                for t in range(M + 1):
                    a[t] += book[j][t]
        for j in range(1, M + 1):
            if a[j] < X:
                a[0] = INF
                break
        ans = min(ans, a[0])
    if ans >= INF:
        ans = -1
    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)]
ans=float('inf')
#2のn乗通り
for i in range(1,2**n):
    rikaido = [0]*m
    money=0
    for j in range(n):
        #組み合わせの処理
        if i>>j&1:
            money+=ca[j][0]
            for k in range(1,m+1):
                rikaido[k-1]+=ca[j][k]
        for l in range(m):
            #全て理解度がx以上の時にかかるコストの最小値を計算する。
            if all(rikaido[l] >= x for l in range(m)):
                ans=min(money,ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

books = []
prices = []
for _ in range(n):
    a = list(map(int, input().split()))
    c = a.pop(0)
    prices.append(c)
    books.append(a)

books = np.array(books)

ans = 10 ** 7
for i in range(2 ** n):
    sel = np.zeros(m)
    price = 0

    for j in range(n):
        if (i >> j) & 1:
            sel += books[j]
            price += prices[j]
    if (sel >= x).all() and price < ans:
        ans = price

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

Submission status: Accepted

Solution code:
from itertools import product
n, m, x = map(int, input().split())
costs = []
gets = []
for i in range(n):
    cost, *argo = map(int, input().split())
    costs.append(cost)
    gets.append(argo)

    
bits_list = list(product([0,1], repeat=n))
min_cost = float('inf')
cnt = 0
for bits in bits_list:
    tmp_cost = 0
    tmp_argo = [0] * m
    for i, v in enumerate(bits):
        if v:
            tmp_cost += costs[i]
            for j, p in enumerate(gets[i]):
                tmp_argo[j] += p
                
    if all(map(lambda X:X>=x, tmp_argo)):
        min_cost = min(min_cost, tmp_cost)
        cnt = 1
if cnt:
    print(min_cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
B=[list(map(int,input().split())) for i in range(n)]
ANS = 1 << 100
for i in range(1 << n):
    SCORE = [0] * m
    MONEY = 0
    for j in range(n):
        if (1 << j) & i != 0:
            MONEY+=B[j][0]
            for k in range(m):
                SCORE[k] += B[j][k+1]
    if min(SCORE) >= x:
        ANS = min(ANS,MONEY)
if ANS == 1 << 100:
    print(-1)
else:
    print(ANS)

Submission status: Accepted

Solution code:

n,m,k=map(int,input().split())
A=[]
for i in range(n):
    row=list(map(int,input().split()))
    A.append(row)
mn=10**9
for i in range(int(2**n)):
    x=bin(i)[2:]
    x=("0"*(n-len(x)))+x
    curr=[0 for ptr in range(m)]
    s=0
    for j in range(n):
        if(x[j]=="1"):
            s+=A[j][0]
            curr=[curr[ptr]+A[j][ptr+1] for ptr in range(m) ]

    curr=[curr[ptr]>=k for ptr in range(m)]
    curr=list(set(curr))
    if(curr==[True]):
        if(s<mn):
            mn=s
if(mn==10**9):
    print(-1)
else:
    print(mn)

Submission status: Accepted

Solution code:
import numpy as np
from numpy import array


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

a = array(a)

c_min = 0
flag = False

for i in range(1, 2 ** n ):
    b = np.zeros(m+1)

    for k in range(n):
        if ((i >> k) & 1):
            b += a[k]
    
    if np.all(b[1:] >= x):
        if flag == False:
            c_min = b[0]
            flag = True
        else:
            c_min = min(c_min, b[0])
        

c_min = int(c_min)

if flag == False:
    c_min = -1

print(c_min)

Submission status: Accepted

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

#ビット全探索。bin(i)の各桁を要素に対応させる。
for i in range(2**n):
    flag=0
    bought_text=np.array([0 for j in range(m+1)])
    for j in range(n):
        #0bxxx1と0b0001の比較(＆は論理積)
        if((i>>j)&1):
            bought_text+=text[j]
    for k in range(m):
        if bought_text[k+1]<x:
            flag=1
            break
    if flag==0:
        cost.append(bought_text[0])
print(min(cost) if cost else "-1")

Submission status: Accepted

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

INF = 9999999999
ans = INF
for i in range(2 ** N):
    price = []
    rikaido = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            price.append(C[j])
            for k in range(M):
                rikaido[k] += A[j][k]
    for l in range(M):
        if rikaido[l] < X:
            break
    else:
        ans = min(ans, sum(price))

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

Submission status: Accepted

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

    result = 10 ** 5 * 12 + 1
    for i in range(2 ** N):
        b = ('0' * N + format(i, 'b'))[-N:]
        r = [0] * M
        sub_res = 0
        for j, s in enumerate(b):
            if int(s) == 1:
                sub_res += C[j]
                for k in range(M):
                    r[k] += A[j][k]
        if all([rx >= X for rx in r]):
            result = min(result, sub_res)
    if result != 10 ** 5 * 12 + 1:
        print(result)
    else:
        print(-1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
inf = 10**9
n, m, x = map(int, input().split())
a = [0] * n
c = [0] * n
y = [0] * n
for i in range(n):
    data = list(map(int, input().split()))
    c[i] = data[0]
    a[i] = data[1:]
ans = inf
for i in range(2**n):
    money = 0
    know = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            money += c[j]
            for k in range(m):
                know[k] += a[j][k]
    for z in know:
        if z < x:
            break
    else:
        ans = min(ans, money)

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

Submission status: Accepted

Solution code:
inf = 10**9
n, m, x = map(int, input().split())
a = [0] * n
c = [0] * n
y = [0] * n
for i in range(n):
    data = list(map(int, input().split()))
    c[i] = data[0]
    a[i] = data[1:]
ans = inf
for i in range(2**n):
    lis = [0]*n
    money = 0
    know = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            money += c[j]
            for l in range(m):
                know[l] += a[j][l]
    for z in know:
        if z < x:
            break
    else:
        ans = min(ans, money)

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

Submission status: Accepted

Solution code:
def main():
    N,M,X=map(int, input().split())
    A=[list(map(int, input().split())) for _ in range(N)]
    ans=10**10
    for i in range(2**N):
        b=i+2**N
        c=0
        l=[0]*M
        ok=True
        for j in range(N):
            if b>>j&1 == 1:
                c+=A[j][0]
                for k in range(M):
                    l[k]+=A[j][k+1]
        for x in l:
            if x < X: ok = False 
        if ok:
            ans = min(ans, c)
    if ans==10**10: print('-1')
    else: print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N,M,X = map(int, input().split())
List = [list(map(int, input().split())) for i in range(N)]
#N,M,X=3,3,10
#List=[[60, 2, 2, 4], [70, 8, 7, 9], [50, 2, 3, 9]]

#print(List)
cost=1200100

for i in range(2**N-1):
    price=0
    num=format(i+1,'0{}b'.format(N))
    arg=[0]*M #それぞれのアルゴリズムの理解度
    for e in range(N):
        if  num[N-1-e]=="1":
            for u in range(M):
                arg[u]+=List[e][u+1]
            price+=List[e][0]  
    b=1
    #print(arg)
    #print(price)
    for t in range(M):
        if  not arg[t]>=X:
            b=2
        #print(b)
    if price<=cost and b==1:
        cost=price
if cost==1200100:
    print("-1")
else:
    print(cost)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    n, m, x = map(int, readline().split())
    bookcosts = [] 
    data = [] 
    for _ in range(n):
        c, *d = map(int, readline().split())
        bookcosts.append(c)
        data.append([i for i in d])
    INF = int(1e9)
    #bit全探索
    ans = INF
    for i in range(1<<n):
        cost = 0
        score = [0 for _ in range(m)]
        for j in range(n):
            if (i>>j) & 1:
                #j番目のbookをかう
                #j番目のbookを買うとcostは増える
                cost += bookcosts[j]
                #j番目のbookを買うと理解度が上がる
                for k in range(m):
                    score[k] += data[j][k]
        #全ての理解度がx以上か判定する
        f = True
        for j in range(m):
            if score[j] >= x:
                pass
            else:
                f = False
        
        if f:
            ans = min(cost, ans)

    if ans == INF:
        print(-1)
    else:
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000000)
from collections import deque 
INF = int(1e9)
ans = INF
def main():
    N, M, X = map(int, readline().split())
    costs = []
    score = []
    for _ in range(N):
        c, *d = map(int, readline().split())
        costs.append(c)
        score.append([i for i in d])
    dq = deque()
    def dfs():
        global ans
        if len(dq) == N:
            cost = 0
            sumScore = [0 for _ in range(M)]
            for i in range(N):
                if dq[i]:
                    cost += costs[i]
                    for j in range(M):
                        sumScore[j] += score[i][j]
            flag = True 
            for i in range(M):
                if sumScore[i] < X: 
                    flag = False

            if flag:
                ans = min(ans, cost)
                return 
            return 
        for i in range(2): 
            dq.append(i)
            dfs()
            dq.pop()

    dfs()
    if ans == INF:
        print(-1)
    else:
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

C = [row[0] for row in CA]
A = [row[1:] for row in CA]

def solve(N, M, X, C, A):
    result = -1
    for n in range(2**N):
        xs = [0] * M
        r = 0
        for i in range(N):
            if ((1 << i) & n):
                r += C[i]
                for j in range(M):
                    xs[j] += A[i][j]
        if all(X <= xs[j] for j in range(M)):
            if result == -1 or r < result:
                result = r
    return result

print(solve(N, M, X, C, A))

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = []
A = []
for _ in range(N):
    s = list(map(int, input().split()))
    C.append(s[0])
    A.append(s[1:])
ans = float('INF')
for i in range(0, 1 << N):
    scores = [0] * M
    count = 0
    for j in range(N):
        if (i >> j) & 1:
            for s in range(M):
                scores[s] += A[j][s]
            count += C[j]
    if min(scores) < X:
        continue
    else:
        ans = min(ans, count)

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

Submission status: Accepted

Solution code:
def makeComb(num):
    if num == n:
        totalM = [0] * m
        totalC = 0
        for i in range(n):
            if s[i] == 1:
                for j in range(m):
                    totalM[j] += ca[i][j+1]
                totalC += ca[i][0]
        for i in range(m):
            if totalM[i] < x:
                return
        global ans
        ans = min(ans, totalC)
        return

    makeComb(num+1)
    s[num] = 1
    makeComb(num+1)
    s[num] = 0

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

ca = [0] * n
for i in range(n):
    ca[i] = list(map(int, input().split()))

INF = 1001001001
ans = INF

s = [0] * n
makeComb(0)

if ans == INF:
    ans = -1
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())))

minCost = 12 * (10**5)
count = 0

for i in range(2**N):
    total = 0
    flag = 1
    B = [0] * M
    for j in range(N):
        if ((i >> j) & 1):
            total = total + a[j][0]
            for k in range(M):
                B[k] = B[k] + a[j][k + 1]
    for l in range(M):
        if B[l] < X:
            flag = 0
    if flag:
        minCost = min(minCost,total)
    count = count + flag

if count:
    print(minCost)
else:
    print("-1")

Submission status: Accepted

Solution code:
from itertools import product

N, M, X = map(int, input().split())
INF = 10**15
ans = INF
cl, al  = [], []
for _ in range(N):
    c, *a, = map(int, input().split())
    cl.append(c)
    al.append(a)

for i in product(range(2), repeat=N):
    b = [0]*M
    tc = 0
    for j, k in enumerate(i):
        if k:
            tc += cl[j]
            for o, p in enumerate(al[j]):
                b[o] += p
    if all(map(lambda x:x>=X, b)):
        ans = min(ans, tc)
print(ans if ans!=INF else -1)

Submission status: Accepted

Solution code:
n, m, X = map(int, input().split())
c = [ 0 for i in range(n)]

x = [ [0 for i in range(m)] for j in range(n)]

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

# print(c)
# print(x)
ans = 1e9
for mask in range(2**n):
    tans = 0
    skill = [0 for i in range(m)]
    for i in range(n):
        if (mask >> i) & 1 > 0:
            tans += c[i]
            for j in range(m):
                skill[j] += x[i][j]
    suc = True
    for i in range(m):
        if skill[i] < X:
            suc = False
            break

    if suc:
        ans = min(ans, tans)

if ans > 1e8:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
blist = []
def createBitline(N, p, bl):
	if(N == p and len(bl) == N):
		blist.append(bl)
	else:
		createBitline(N, p + 1, bl + "0")
		createBitline(N, p + 1, bl + "1")
 
def checkClear(X, list):
	for i in range(1, len(list)):
		if int(list[i]) < X:
			return False
	return True
 
listCA = []
N,M,X = map(int, input().split())
for i in range(N):
	listCA.append(input().split())
createBitline(N, 0, "")
cost = []
for x in range(len(blist)):
	sumCA = [0] * (M + 1)
	for i in range(N):
		if blist[x][i] == "1":
			for j in range(len(listCA[i])):
				sumCA[j] += int(listCA[i][j])
	if checkClear(X, sumCA):
		cost.append(sumCA[0])
if cost:
	print(min(cost))
else:
	print('-1')

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    import itertools
    
    N,M,X=MI()
    C=[0]*N
    A=[]
    for i in range(N):
        ca=LI()
        C[i]=ca[0]
        A.append(ca[1:])
        
    ans=10**10
    for ite in itertools.product([0,1], repeat=N):
        score=[0]*M
        temp=0
        for i in range(N):
            if ite[i]:
                temp+=C[i]
                for j in range(M):
                    score[j]+=A[i][j]
        if min(score)>=X:
            ans=min(ans,temp)
            
    if ans==10**10:
        ans=-1
    print(ans)
                
            
       

main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
A=[list(map(int,input().split()))for a in range(n)]
mi=[10**7]

for i in range(2**n):
  und=[0]*m
  money=0
  for j in range(n):
    if (i >> j)&1:
      money+=A[j][0]
      for u in range(m):
        und[u]+=A[j][u+1]
  if all(und[s]>=x for s in range(m)):    
    mi.append(money)
   
print(min(mi) if min(mi)!=10**7 else -1)

Submission status: Accepted

Solution code:
import copy

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

li = [[0 for i in range(M+1)] for j in range(N)]

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

sumLiA = [0 for i in range(M+1)]
sumLi = copy.deepcopy(sumLiA)
costLi = []
flag = 1

for pat in range(2**N):
  pat = format(pat, '012b')
  for bookNum in range(N):
    if pat[-bookNum-1] == '1':
      for i in range(M+1):
        sumLi[i] += li[-bookNum-1][i]
  for liN in range(1, M+1):
    if sumLi[liN] < X:
      flag = 0
      break
  if flag == 1:
    costLi.append(sumLi[0])
  flag = 1
  sumLi = copy.deepcopy(sumLiA) 

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