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:
#!/usr/bin/env python3
# bit全探索

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

# calc
ans = []
for s in range(1<<n):
    rikaido = [0 for _ in range(m)]
    cost = 0 
    for i in range(n):
        if s>>i&1:
            cost += c[i]
            for j in range(m):
                rikaido[j] += a[i][j]
    ok = True
    for j in range(m):
        if rikaido[j] < x:
            ok = False
            break
    if ok: 
        ans.append(cost)

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

Submission status: Accepted

Solution code:
from itertools import combinations

n, m, x = list(map(int, input().split()))
c = []
a = []

# c, aにデータを用意
for i in range(n):
    tmp = list(map(int, input().split()))
    c.append(tmp[0])
    a.append([])
    
    for j in range(1, m + 1):
        a[i].append(tmp[j])

money_min = -1
comb = []
# 組み合わせを用意
for l in range(n):
    tmp = combinations(range(n), l + 1)
    for i in tmp:
        comb.append(i)
    
# 組み合わせごとに考える
for el in comb:
    ables = []
    money = 0        
    scores = []

    # scoreに0をいれる
    for i in range(m):
        scores.append(0)

    # 組み合わせを足し合わせる
    for n in el:
        money += c[n] # 金
        for i in range(m):
            scores[i] += a[n][i] # 習得度

    # 判定
    for i in range(m):
        ables.append(scores[i] >= x)

    # 良ければ金額更新
    if all(ables):
        money_min = money if money_min < 0 or money_min > money else money_min

print(money_min)

Submission status: Accepted

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

A = [[] for _ in range(N)]
c = [0] * N

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

INF = 10 ** 9
ans = INF

for s in range(0, 1 << N):
    smart = [0] * M
    cost_sum = 0
    for i in range(N):
        if (s >> i) % 2 == 0: continue
        cost_sum += c[i]
        for j in range(M):
            smart[j] += A[i][j]
    ok = True
    for j in range(M):
        if smart[j] < X:
            ok = False
    if ok:
        ans = min(ans, cost_sum)

if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
#bit全探索
n,m,x=map(int,input().split())
a=[]
for i in range(n):
    ai=list(map(int,input().split()))
    a.append(ai)

#可能判定
maxi=[0 for i in range(m)]
for i in range(n):
    for j in range(m):
        maxi[j]+=a[i][j+1]
for i in range(m):
    if maxi[i]<x:
        print(-1)
        exit()

mini=100000000
#全探索
for i in range(2**n):
    d=[]
    for j in range(n):
        if((i>>j)& 1):
            d.append(j)
    b=[0 for j in range(m)]
    #得た能力
    c=0
    #お金
    for j in d:
        c+=a[j][0]
        for k in range(m):
            b[k]+=a[j][k+1]
    l=0
    for j in b:
        if j<x:
            l=1
    if l==0:
        mini=min(mini,c)

print(mini)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N, M, X = MAP()
CA = [LIST() for _ in range(N)]

ans = INF
for x in product([0, 1], repeat=N):
	#print(x)
	s = np.zeros((M,))
	tmp = 0
	for i in range(N):
		if x[i]:
			C, *A = CA[i]
			#print(C)
			#print(A)
			tmp += C
			#print(np.array(A))
			s += np.array(A)
			#print(s)
	s = s.tolist()
	#print("s={}".format(s))
	#print(skill, cost)
	if all(p >= X for p in s):
		ans = min(ans, tmp)

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

Submission status: Accepted

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

prices = []
skills = []
patterns = 2 ** n
ans = 10 ** 10 * n
for i in range(patterns - 1, -1, -1):
    pattern = i
    skill = [0] * m
    price = 0
    for book in books:
        if pattern & 1 == 1:
            price += book[0]
            for j in range(1, m + 1):
                skill[j-1] += book[j]
        pattern >>= 1
    prices.append(price)
    skills.append(skill)
    flg = True
    for k in skill:
        if k < x:
            flg = False
            break
    if flg:
        if ans > price:
            ans = price
if ans == 10 ** 10 * n:
    ans = -1
print(str(ans))

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(n)]
a=float('inf')
for i in range(2**n):
  S=[0]*(m+1)
  for j in range(n):
    if (i>>j)&1:
      S=[S[k]+A[j][k] for k in range(m+1)]
  if all([s >= x for s in S[1:]]):
    a=min(a,S[0])
print(-1 if a==float('inf') else a)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
b=2**n
lst=[]
for i in range(n):
  lst.append(list(map(int,input().split())))
Cost=[]
for i in range(1,b+1):
  skill=[0]*m
  cost=0
  s=(str(bin(i))[2:]).zfill(n)
  for k in range(n):
    if s[k]=='1':
      for l in range(m):
        skill[l]+=lst[k][l+1]
      cost+=lst[k][0]
  for j in range(m):
    if skill[j]<x:
      break
    if j==m-1 and x<=skill[j]:
      Cost.append(cost)


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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
rikai = []
ans = -1
for i in range(n):
    a = list(map(int,input().split()))
    rikai.append(a)
for i in range(2**n):
    money = 0
    now = [0]*m
    for j in range(n):
        if ((i >> j)&1):
            money += rikai[j][0]
            for k in range(m):
                now[k] += rikai[j][k+1]
    if min(now) >= x:
        if ans == -1:
            ans = money
        else:
            ans = min(ans,money)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
 
N, M, X = MAP()
CA = [LIST() for _ in range(N)]

ans = INF

for x in product([0, 1], repeat=N):
	#print(x)
	skill = [0]*M
	cost = 0
	for i in range(N):
		if x[i] == 1:
			cost += CA[i][0]
			for j in range(M):
				skill[j] += CA[i][j+1]
	#print(skill, cost)
	if all(p >= X for p in skill):
		ans = min(ans, cost)

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

Submission status: Accepted

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

for i in range(2**N):
    score=[0]*M
    price=0
    for j in range(N):
        if ((i>>j) & 1):
            price+=int(A[j][0])
            for k in range(M):
                score[k]+=int(A[j][k+1])
    if sorted(score)[0] >= X:
        ans.append(price)

print(-1 if len(ans)==0 else min(ans))

Submission status: Accepted

Solution code:
import math
def solve(C,A,x,k,s,U):
    if k == 0:
        if min(U) >= x:
            return s
        else:
            return math.inf
    
    else:
        s_use = s+C[k-1]
        U_use = [u+a for u,a in zip(U,A[k-1])]

        return min(solve(C,A,x,k-1,s,U),solve(C,A,x,k-1,s_use,U_use))

        

def main():
    from sys import stdin
    n,m,x = map(int,stdin.readline().rstrip().split())
    C = []
    A = []
    for _ in range(n):
        temp = list(map(int,stdin.readline().rstrip().split()))
        C.append(temp[0])
        A.append(temp[1:])
    
    U = [0]*m
    ans = solve(C,A,x,n,0,U)
    print(ans if ans != math.inf else -1)
    
main()

Submission status: Accepted

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

    ans = 10**5*13
    for flag in range(1 << N):
        cost = 0
        skill = [0] * M
        for i in range(N):
            if flag >> i & 1:
                cost += C[i]
                for j in range(M):
                    skill[j] += A[i][j]
        if all(sk >= X for sk in skill):
            ans = min(ans, cost)
    if ans == 10**5*13:
        print(-1)
    else:
        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)]

books = []

book_prices = float('inf')

for i in range(2 ** N):
    book = 0
    skill_points = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            book += CA[j][0]
            for k in range(1, M + 1):
                skill_points[k - 1] += CA[j][k]
    X_overs = filter(lambda x: x >= X, skill_points)
    if(len(list(X_overs)) == M):
        book_prices = min(book_prices, book)

print('-1' if book_prices == float('inf') else book_prices)

Submission status: Accepted

Solution code:
import numpy as np


n,m,x = map(int,input().split())
mat = []
for _ in range(n):
    mat.append(list(map(int, input().split())))
mat = np.array(mat)
c_arr = mat[:,0]
a_arr = mat[:,1:]
money = -1
for i in range(1, 2**n):
    l = [bool(x) for x in map(int, format(i, f'0{n}b'))]
    money_tmp = sum(c_arr[l])
    if money != -1 and money < money_tmp:
        continue
    
    sum_li = np.sum(a_arr[l].reshape(-1, m), axis=0)
    if all(sum_li>=x):
        money = money_tmp

print(money)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m,x=map(int,input().split())
a=[[] for ii in range(n)]
for ii in range(n):
  a[ii]=list(map(int,input().split()))

r=[0]*(m+1)
for jj in range(m+1):
  r[jj]+=sum([a[ii][jj] for ii in range(n)])

import numpy as np
def lambda_d(ii,r,km):
  if max(km[1:m+1])<=0:
    return 0,True

  rx=[r[jj]-a[ii][jj] for jj in range(m+1)]
  kx=[km[jj]-a[ii][jj] for jj in range(m+1)]
  if ii==n-1:
    #print(kx[1:m+1])
    if max(kx[1:m+1])>0:
      return 0,False
    else:
      return a[ii][0],True
    
  lt,tft=lambda_d(ii+1,rx,kx)
  lf,tff=lambda_d(ii+1,r,km)
  if tft or tff:
    #print(ii,tff,tft,lf,lt+a[ii][0])
    if not tft:
      return lf,tff
    elif not tff:
      return lt+a[ii][0],tft
    else:
      return min(lt+a[ii][0],lf),True
  else:
    return 0,False

km=[x]*(m+1)
l0,tf=lambda_d(0,r,km)
if not tf:
  print(-1)
else:
  print(l0)

Submission status: Accepted

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

for i in range(1, 1 << N):
    cst=0
    x=[0]*M
    for j in range(N):
        if i & (1 << j) != 0:
            cst+=mat[j][0]
            for k in range(M):
                x[k]+=mat[j][k+1]
    all=True
    for j in x: 
        if j < X:
            all=False
            break
    if all:
        if cost<0:
            cost=cst
        else:
            cost=min(cost, cst)
print(cost)

Submission status: Accepted

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

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
for i in range(1 << N):
    t = [0] * M
    c = 0
    for j in range(N):
        if (i >> j) & 1 == 0:
            continue
        c += C[j]
        for k in range(M):
            t[k] += A[j][k]
    if all(x >= X for x in t):
        if result == -1:
            result = c
        else:
            result = min(result, c)
print(result)

Submission status: Accepted

Solution code:
INF = pow(10, 9)


def main():
    n, m, x = map(int, input().split())
    i = 0
    c = []
    a = []

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

    ans = INF
    for i in range(2**n):
        tmp = [0 for i in range(m)]
        cost = 0
        flag = True
        for j in range(n):
            if ((i >> j) & 1) == 1:
                tmp = [x+y for x, y in zip(tmp, a[j])]
                cost += c[j]
        # print(tmp)
        for j in range(m):
            if tmp[j] < x:
                flag = False
                break
        # print(cost)
        if flag == True:
            if cost < ans:
                ans = cost
    print(ans) if ans != INF else print(-1)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
c=[]
inf=10**9
result=inf
for _ in range(n):
    books=list(map(int,input().split()))
    c.append(books[0])
    a.append(books[1:])
    
for i in range(1<<n):
  cnt=0
  rikaido=[0]*m
  for j in range(n):
    if (i>>j)&1:
      for k in range(m):
        rikaido[k]+=a[j][k]
      cnt+=c[j]
    else:
      pass
  if min(rikaido)>=x:
    result=min(result,cnt)

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

Submission status: Accepted

Solution code:
import numpy as np
N,M,X= map(int,input().split())
a = []
d = 0
e = False
f = []
z = 0
for i in range(N):
    a.append([])

for i in range(N):
    a[i]= [int(i) for i in input().split()]

for i in range(2 ** N):
    b = np.array([0 for _ in range(M + 1)])
    d = True
    for j in range (N):

        if ((i >> j) & 1):
            b = np.array(a[j]) + b
    z = z + 1
    for k in range(M):
        if b[k + 1] < X:
            d = False
    if d:
        f.append(b[0].tolist())
        e = True
if e:
    print(min(f))
else:
    print("-1")

Submission status: Accepted

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

for i in range(2**n):
    cost = 0
    a = [0]*m
    for j in range(n):
        if (i >> j) & 1:
            cost += c[j][0]
            for k in range(m):
                a[k] += c[j][k+1]
    if min(a) >= x:
        flag = True
        ans = min(ans, cost)

print(ans if flag else -1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
numlist = []
minimum = -1
for i in range(n):
    numlist.append(list(map(int, input().split())))
for i in range(1<<n):
    result = [0] * (m+1)
    for j in range(n):
        if(i>>j & 1 == 1):
            for k in range(m+1):
                result[k] += numlist[j][k]
    for k in range(m):
        if(result[k+1] < x): break
    else:
        if(minimum > result[0] or minimum == -1): minimum = result[0]
print(minimum)

Submission status: Accepted

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

a = []
ans1=[]
for i in range(N):
    a.append(list(map(int,input().split())))
    
for i in range(2**N):
    # print("i=",i)
    x = [0]*M
    c = 0
    flag = True
    
    for j in range(N):
        if ((i >> j) & 1):
            c += a[j][0]
            for k in range(M):
                x[k] += a[j][k+1]
    
    for j in range(M):
        if x[j] < X:
            flag =False
    if flag == True:
        ans1.append(c)
    # print(x)
    # print("c=",c)

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

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split(" "))
hon = []
check = False
for i in range(n):
    hon.append(list(map(int, input().split(" "))))
mini = n * (10 ** 10)
for bit in range(2 ** n):
    nouryoku = [0 for k in range(m + 1)]
    for j in range(n):
        mask = 1 << j
        if bit&mask:
            for k in range(m + 1):
                nouryoku[k] += hon[j][k]
    temp = 1
    for i in range(1, m + 1):
        temp *= nouryoku[i] // x
    if temp >= 1:
        check = True
        if nouryoku[0] < mini:
            mini = nouryoku[0]
if check:
    print(mini)
else:
    print(-1)

Submission status: Accepted

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

for i in range(2**N):
    price = 0
    point = [0]*M
    for j in range(N):
        if (i >> j) & 1 == 1:
            price += listA[j][0]
            for k in range(M):
                point[k] += listA[j][k+1]
    if min(point) >= X:
        ans = min(ans, price) if ans != -1 else price
print(ans)

Submission status: Accepted

Solution code:
(N, M, X), *T = [[*map(int, line.split())] for line in open(0)]

ans = 12345678
for bit in range(1, 2**N):
    t = [T[i] for i in range(N) if bit & (1 << i)]
    c, *a = map(sum, zip(*t))
    if all(e >= X for e in a):
        ans = min(ans, c)

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

Submission status: Accepted

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes) if b else print(no)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx
# from bisect import bisect_left,bisect_right
n,m,x=n1()
ca=n3(n)
ans=9999999999

import itertools
book=list(itertools.product([0,1], repeat=n))
price=[]
for line in book:
    p=0
    for i in range(n):
        if line[i]==1:
            p+=ca[i][0]
            
    price.append(p)
for i in range(len(book)):
    t=book[i]
    s=[0]*m
    for j in range(n):
        if t[j]==1:
            s=[s[k]+ca[j][k+1] for k in range(m)]
    if len([y for y in s if y>=x])==m:
        ans=min(ans,price[i])
if ans==9999999999:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M,X = map(int,input().split())
data = []
minval = -1
for n in range(N):
    data.append(list(map(int,input().split())))
for ptn in range(2**N):
    sumchk = [0]*(M)
    sumpri = 0
    for bit in range(N):
        if ptn & (1 << bit) != 0:
            sumpri += data[bit][0]
            for x in range(M):
                sumchk[x] += data[bit][x+1]
    flag = True
    for x in range(M):
        if sumchk[x] < X:
            flag = False
            break
    if flag:
        if minval == -1:
            minval = sumpri
        else:
            if minval > sumpri:
                minval = sumpri
print(minval)

Submission status: Accepted

Solution code:
import numpy as np

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

C = [0]*N
A = np.zeros((N, M), int)
for i in range(N):
    C[i], *A[i] = map(int, input().split())

ans = 12345678
for bit in range(1, 2**N):
    c = [C[i] for i in range(N) if bit & (1 << i)]
    a = [A[i] for i in range(N) if bit & (1 << i)]
    a = np.array(a)

    if all(a.sum(0) >= X):
        ans = min(ans, sum(c))

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

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())
flg=np.zeros((m+1),dtype=int)
minimn=-1
data=np.zeros((n,m+1))
for i in range(n):
    data[i]=list(map(int,input().split()))
for i in range(2**n):
    flg=np.zeros((m+1))
    for j in range(n):
        if (i>>j)&1:
            flg+=data[j]
    if all(flg[1:]>=x):
        if minimn==-1:
          minimn=flg[0]
        elif flg[0]<minimn:
          minimn=flg[0]
print(int(minimn))

Submission status: Accepted

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

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

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

inf = 10 ** 9
min_cash = inf

for j in range(2**n):
    sum_cash = 0
    al = [0]*m
    for k in range(n):
        if ((j>>k) & 1):
            sum_cash += c[k]
            for l in range(m):
                al[l] += a[k][l]
       
    f = 1   
    for j in range(m):
        if al[j] < x:
            f = 0

    if f:
        min_cash = min(min_cash,sum_cash)

if min_cash == inf:
    min_cash = -1

print(min_cash)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
books = []
book_total_price = []
for _ in range(n):
    book = list(map(int, input().split()))
    books.append(book)
 
for i in range(2**n):
    reference_book = []
    book_price = 0
    for j in range(n):
        if (i >> j) & 1:
            reference_book.append(books[j])
            book_price += books[j][0]
    err = 0
    for k in range(1, m+1):
        r = [row[k] for row in reference_book]
        if sum(r) < x:
            err += 1
    if err == 0:
        book_total_price.append(book_price)
if book_total_price == []:
    print('-1')
else:
    print(min(book_total_price))

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
books = []
ans = float('inf')
for _ in range(n):
    book = list(map(int, input().split()))
    books.append(book)

for i in range(2**n):
    count = [0] * m
    book_price = 0
    for j in range(n):
        if (i >> j) & 1:
            book_price += books[j][0]
            for k in range(1, m+1):
                count[k-1] += books[j][k]
    check = True
    for j in count:
        if j < x:
            check = False
            break
    if check:
        ans = min(ans, book_price)
if ans == float('inf'):
    print('-1')
else:
    print(ans)

Submission status: Accepted

Solution code:


sankouNum, argoNum, rikaido = map(int, input().split())

sankouCosts = []
sankouEffects = []

for _ in range(sankouNum):
    cost, *effect = map(int, input().split())

    sankouCosts.append(cost)
    sankouEffects.append(effect)


ans = float('inf')

# 買う/買わないの全組み合わせの生成
import itertools
for params in itertools.product([0,1], repeat=sankouNum):

    currentCost = 0
    currentRikaidos = [0] * argoNum
    # 一つの組み合わせごとのループ
    for si, param in enumerate(params):
        if param == 0:
            # si番目の参考書は買わない
            pass
        elif param == 1:
            # si番目の参考書を買う
            currentCost += sankouCosts[si]
            for ri in range(argoNum):
                currentRikaidos[ri] += sankouEffects[si][ri]
    # 理解度を満たすか判定
    if min(currentRikaidos) >= rikaido:
        # 満たす場合、ansより小さければ現時点での最小コストとなる
        ans = min(ans, currentCost)

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

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
inf = 10**9
result = inf
A=[]
C=[]
for _ in range(n):
	books=list(map(int, input().split()))
	C.append(books[0])
	A.append(books[1:])
for i in range(1<<n):
	cnt = 0
	rikaido = [0]*m
	for j in range(n):
		if (i>>j)&1:
			for k in range(m):
				rikaido[k]+=A[j][k]
			cnt += C[j]
		else:
			pass
	if min(rikaido)>=x:
		result = min(result, cnt)
if result == inf:
	print(-1)
else:
	print(result)

Submission status: Accepted

Solution code:
import itertools
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
        b = [int(i) for i in bin(i)[2:]]
        for select_u, select_m in itertools.compress(zip(UNDERSTAND, MONEY), b[::-1]):
            money += select_m
            for k in range(m):
                understand[k] += select_u[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:
# -*- coding: utf-8 -*-
# モジュールのインポート
import numpy as np


def get_input() -> tuple:
    """標準入力の取得

    Returns:
        tuple -- 標準入力
    """
    N, M, X = list(map(int, input().split()))
    C = []
    A = []
    for n in range(N):
        line = list(map(int, input().split()))
        C.append(line[0])
        A.append(line[1:])

    return N, M, X, C, A


def main(N: int, M: int, X: int, C: list, A: list) -> None:
    """求解処理.\n
    bit全探索を行う.

    Arguments:\n
        N {int} -- 参考書の数
        M {int} -- 学びたいアルゴリズムの数
        X {int} -- 目標とする理解度
        C {list} -- 参考書の値段
        A {list} -- 各参考書によるアルゴリズムの理解度
    """
    # 計算を簡単にするため、numpy配列にしておく
    C = np.array(C)
    A = np.array(A)

    # bit全探索
    result = sum(C)
    canAchieve = False
    for i in range(2**N):
        cost = 0
        skill = np.zeros(M)
        for j in range(N):
            if ((i >> j) & 1):
                cost += C[j]
                skill += A[j]

        if min(skill) >= X:
            result = min(result, cost)
            canAchieve = True

    if not canAchieve:
        result = -1

    # 結果出力
    print(result)


if __name__ == "__main__":
    N, M, X, C, A = get_input()
    main(N, M, X, C, A)

Submission status: Accepted

Solution code:
import numpy as np,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,M,X = LI()
CA = np.array([LI() for _ in range(N)])
ans = float('INF')
for i in range(2**N):
    bit = np.array([[i>>j&1 for j in range(N)]]).T
    temp = (CA*bit).sum(axis=0)
    if (temp[1:]>=X).all():
        ans = min(ans,temp[0])
print(ans if ans!=float('INF') else -1)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
keep = []
ans = 10**10
for i in range(n):
    c = list(map(int, input().split()))
    keep.append(c)
for j in range(2**n):
    bag = [0] * m
    total = 0
    check = 1
    for k in range(n):
        if ((j >> k) & 1):
            for l in range(m):
                bag[l] += keep[k][l + 1]
            total += keep[k][0]
    for a in range(m):
        if bag[a] < x:
            check *= 0
    if ans * check > total:
        ans = total
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

f = False
res = 10**7
for i in range(2**N):
    kane = 0
    rikaido = [0]*M
    for j in range(N):
        if (i>>j)&1:
            kane += sankousyo[j][0]
            for k in range(M):
                rikaido[k] += sankousyo[j][k+1]
    if min(rikaido) >= X:
        f = True
        res = min(kane, res)

if f:
    print(res)
else:
    print(-1)

Submission status: Accepted

Solution code:
N,M,X=list(map(int,input().split()))
lines = []

for i in range(N):
	lines.append(list(map(int,input().split())))
pricemin = 1500000
for i in range(2**N):
	price = 0
	count = 0
	A = [0]*M
	for j in range(N):
		if ((i >> j) & 1):
			for k in range(M):
				A[k] += lines[j][k+1]
			price += lines[j][0]
	for j in range(M):
		if A[j] >= X:
			count += 1
	if count == M and pricemin > price:
		pricemin = price
if pricemin == 1500000:
	print('-1')
else:
	print(pricemin)

Submission status: Accepted

Solution code:
# coding: utf-8
N, M, X = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(N)]
n = len(C)
m = -1
for i in range(2 ** n):
    A = [0 for i in range(M+1)]
    total = 0
    for j in range(n):
        if((i >> j) & 1):
            A = [a + b for a, b in zip(A, C[j])]
            B = [k for k in range(1, M+1) if A[k] < X]
            if len(B) == 0:
                if m == -1:
                    m = A[0]
                else:
                    m = min(m, A[0])
                break
print(m)

Submission status: Accepted

Solution code:
#入力受け取り

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

#指定した回数リストを取り込む

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

#最小値を更新するため、適当に大きな値を設定

ans = 91912922191

#総当たりする場合の試行回数

for buy in range(2 ** n):

#M長の空リストを作成する

    C = [0] * m

#値段の合計値の受け皿

    cost = 0
 
#？？？
 
    for i in range(n):

#購入した場合は加算する

        if (buy >> i) & 1:
            cost += X[i][0]

#１番目からM番目の要素を空リストに加算していく
#Cは0～Mをリストに、リストXから取得する

            for j in range(1, m + 1):
                C[j - 1] += X[i][j]

#すべての理解度から一番小さなものを取得し、それがxを超えているか確認

    if min(C) >= x:

#小さい方をansに代入

        ans = min(ans, cost)

#値が初期値よりも小さければ出力させる

if ans < 91912922191:
    print(ans)
else:
    print(-1)