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 = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(N)]

def calc(state):
    ret = 0
    S = [0] * M
    for i, B in enumerate(A):
        if ((1 << i) & state) == 0:
            continue
        for j, a in enumerate(B[1:]):
            S[j] += a
        ret += B[0]
    if all(s >= X for s in S):
        return ret
    return 10**18

ans = 10**18
for state in range(1 << N):
    ans = min(ans, calc(state))

print(ans if ans < 10**18 else -1)

Submission status: Accepted

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

import itertools
bit=list(itertools.product([0,1], repeat=n))

ans=10**15

for comb in bit:
    pri=0
    R=[0 for i in range(m)]
    for i in range(n):
        if comb[i]==1:
            pri+=C[i][0]
            for q in range(m):
                R[q]+=C[i][q+1]
    if min(R)>=x:
        ans=min(ans,pri)

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

Submission status: Accepted

Solution code:
import numpy as np

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

C = [0]*N
A = np.array([[0]*M for i in range(N)])

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

min_ans = 10**10
flg = False
for i in range(2**N):
    tmp_A = np.array([0] * M)
    tmp_C = 0
    for j in range(N):
        if ((i >> j) & 1):
            tmp_A += A[j]
            tmp_C += C[j]
    if (tmp_A >= X).sum() == M and tmp_C < min_ans:
        min_ans = tmp_C
        flg = True

if flg:
    print(min_ans)
else:
    print("-1")

Submission status: Accepted

Solution code:
INF = 10**18

N, M, X = map(int, input().split())
C = [0]*N
A = [[] for i in range(N)]
for i in range(N):
    src = list(map(int, input().split()))
    C[i] = src[0]
    A[i] = src[1:]
ans = INF
for i in range(1<<N):
    point = [0]*M
    m = 0
    for j in range(N):
        if i&(1<<j) > 0:
            m += C[j]
            for ii, a in enumerate(A[j]):
                point[ii] += a
    ok = True
    for j in range(M):
        if point[j] < X:
            ok = False
            break
    if ok:
        ans = min(ans, m)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
import itertools

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline

    n,m,x=map(int, readline().rstrip().split())
    memo=[[0 for i in range(m+1)] for j in range(n)]
    for i in range(n):
        memo[i]=list(map(int, readline().rstrip().split()))

    loops=[[0,1] for i in range(n)]

    minCost=9999999999
    for loop2 in list(itertools.product(*loops)):
        cost=0
        loop=list(loop2)
        algo=[0]*m
        for l in range(len(loop)):
            if loop[l]==1:
                cost+=memo[l][0]
                for a in range(m):
                    algo[a]+=memo[l][a+1]
        if min(algo) >=x:
            minCost=min(minCost,cost)
    if minCost==9999999999:
        print(-1)
    else:
        print(minCost)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import product 
input = sys.stdin.readline
N,M,X= map(int,input().split())
CA = [list(map(int,input().split())) for i in range(N)]
C,*A = zip(*CA)
C = np.array(C)
A = np.array(A)

inf = 10**8
ans = inf

l = [1,0]
for c in product(l,repeat=N):
    Y = c * A
    Y = np.sum(Y,axis=1)
    if np.all((Y-X) >= 0):
        ans = min(ans, np.sum(c*C))

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

Submission status: Accepted

Solution code:
from itertools import product
n,m,k = map(int,input().split())
l = list(list(map(int,input().split())) for i in range(n))

a = [0,1]
mi = 10**8
for i in product(a,repeat=n):
  money = 0
  tishiki = list(0 for i in range(m))
  for j in range(n):
    q = i[j]
    if q==1:
      money += l[j][0]
      for e in range(m):
        tishiki[e] += l[j][e+1]
  for v in tishiki:
    if v<k:
      break
  else:
    mi = min(mi,money)
if mi==10**8:
  print(-1)
else:
  print(mi)

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def solve(idx, cur, cost):
    #####
    if(idx==n):
        # print(cur)
        flag = 0
        for el in cur:
            if(el<x):
                flag = 1
                break
        if(flag==0):
            return cost
        else:
            return INF

    cur1 = [0]*m
    for i, el in enumerate(a[idx]):
        cur1[i] += el+cur[i]
    temp1 = solve(idx+1, cur1, cost+c[idx])
    temp2 = solve(idx+1, cur, cost)

    return min(temp1, temp2)

n,m,x = MAP()

c = []
a = []

for _ in range(n):
    temp = LIST()
    c.append(temp[0])
    a.append(temp[1:])

curr = [0]*m
ans = solve(0, curr, 0)
if(ans==INF):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

ans = 10**9

for i in range(2 ** N):
    money = 0
    L = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            money += book[j][0]
            for m in range(M):
                L[m] += book[j][m+1]
    
    for m in range(M):
        if L[m] < X:
            break
    else:
        ans = min(ans, money)

if ans == 10**9:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
import itertools
N, M, X = map(int, input().split())
a = [list(map(int,input().split())) for i in range (N)]
nums = [0,1]
c = float('inf')
for balls in itertools.product(nums, repeat=N):
  g = 1
  for j in range(M):
    if X>sum([balls[i]*a[i][j+1] for i in range(N)]):
      g = 0
  if g == 1:
    c = min(c, sum([balls[i]*a[i][0] for i in range(N)]))
if c != float('inf'):
  print(c)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,X = LI()

    c = []
    s = []
    for _ in range(N):
        x = LI()
        c.append(x[0])
        s.append(x[1:])


    ans = INF
    for i in range(1,2**N):
        t = [0] * M
        b = 1
        cost = 0
        for j in range(N):
            if i & b:
                for k in range(M):
                    t[k] += s[j][k]
                cost += c[j]
            b <<= 1
        for x in t:
            if x < X: break
        else:

            ans = min(ans,cost)
    if ans < INF:
        print(ans)
    else:
        print(-1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

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

ans = 100000000000
for k in range(1, n + 1):
    for cmb in itertools.combinations(range(n), k):
        d = [0] * m
        cost = 0
        for cm in cmb:
            cost += c[cm]
            for i in range(m):
                d[i] += a[cm][i]

        f = True
        for i in range(m):
            if d[i] < x:
                f = False
                break
        if f:
            ans = min(ans, cost)

if ans == 100000000000:
    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())))
min=13*100000

for i in range(2**n):
    s=0
    m1=[0 for i in range(m)]
    for j in range(n):
        if (i>>j&1):
            s+=a[j][0]
            for k in range(m):
                m1[k]+=a[j][k+1]
    for j in range(m):
        if m1[j]<x:
            break
    else:
        if s<min:
            min=s
if min!=13*100000:
    print(min)
else:
    print(-1)

Submission status: Accepted

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

anm = [None] * n
cn = [None] * n
for i in range(n):
    row = list(map(int, input().split(' ')))
    cn[i] = row[0]
    anm[i] = row[1:]

ans = float('inf')
for i in range(2 ** n):
    cost = 0
    ex = [0] * m
    for j in range(n):
        if i >> j & 1:
            cost += cn[j]
            for k in range(m):
                ex[k] += anm[j][k]
    if sum(1 for e in ex if e >= x) == m and ans > cost:
        ans = cost

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    import numpy as np
    # import math
    # import random
    input = stdin.readline


    n, m, x = map(int, input().split())
    cc = [0]*n
    aa = [0]*n
    for i in range(n):
        c, *a = map(int, input().split())
        cc[i] = c
        aa[i] = np.array(a)
    ans = sum(cc)+1
    for i in range(2**n):
        understand = np.array([0]*m)
        total = 0
        for j in range(n):
            if ((i >> j) & 1):
                understand += aa[j]
                total += cc[j]
        if (understand>=x).all() and ans > total:
            ans = total
    if ans == sum(cc)+1:
        print('-1')
    else:
        print(ans)

Submission status: Accepted

Solution code:
N,M,K= list(map(int, input().split()))
C = []
A = []
for _ in range(N):
    c= list(map(int, input().split()))
    C.append(c[0])
    A.append(c[1:])
inf = float('inf')
ans = inf

for i in range(2**N):
    re = [0]*M
    count = 0
    for j in range(N):
        if((i>>j)&1):
            count += C[j]
            for k in range(M):
                re[k] += A[j][k]
    
    flag = True
    for n in range(M):
        if re[n] < K:
            flag = False
    
    if flag:
        ans = min(ans,count)

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

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np
N,M,X=map(int,input().split(' '))
Books=[np.array(list(map(int,input().split(' ')))) for i in range(N)]
A=[0]*M
maxi = sum([Books[i][0] for i in range(N)])+1
ans = maxi
for i in product([0,1],repeat=N):
    tmp = np.array([0]*M)
    t_ans = 0
    for n,j in enumerate(i):
        if j:
            tmp += Books[n][1:]
            t_ans += Books[n][0]
    if tmp.min() >=X:
        ans = min(ans,t_ans)
if ans < maxi:
    print(ans)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import chain, combinations

def powerset(iterable):
    """
    powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
    """
    xs = list(iterable)
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))
# print(len(list(powerset([1,2,3,4,5]))))

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

subsets = list(powerset([i for i in range(N)]))
ans = float('inf')
for item in subsets:
    if not item:
        continue
    tmp = [0] * (M + 1)
    cost = 0
    for idx in item:
        cost += arr[idx][0]
        for i, v in enumerate(arr[idx]):
            tmp[i] += v
    flag = True
    for i in range(1, M+1):
        if X > tmp[i]:
            flag = False
    if flag:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque

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=[]
    for j in range(1,M+1):
        a.append(l[j])
    A.append(a)
ans=10**10
flag=False
for i in range(2**N):
    op=["-"]*N
    for j in range(N):
        if ((i>>j)&1):
            op[N-1-j]="+"
    tmp=0
    l=[0]*M
    for j in range(N):
        if op[j]=="+":
            tmp+=C[j]
            for k in range(M):
                l[k]+=A[j][k]
    f=True
    for j in range(M):
        if l[j]<X:
            f=False
    if f:
        flag=True
        ans=min(ans,tmp)

if flag:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:


import numpy as np


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

ans = 10**10
for bit in range(2**N):
    tc = 0
    ta = np.zeros(M)
    for i in range(N):
        if bit & (1 << i):
            tc += C[i]
            ta += np.array(A[i])
    if min(ta) >= X:
        ans = min(tc, ans)
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m,x = map(int,input().split())
    c = []
    for i in range(n):
        cc = list(map(int,input().split()))
        c.append(cc)
    tmp = 2 ** n
    ans = 10**8

    bi=str(format(tmp,"b"))#2進表現に
    for k in range(tmp):
        anstmp = 0
        ary = [0] * m
        for i in range(n):
            if ((k >> i) & 1):
                anstmp += c[i][0]
                for j in range(1,m+1):
                    ary[j-1] += c[i][j]

        
        flg = True
        for j in range(m):
            if ary[j] < x:
                flg = False
                break
        if anstmp < ans and flg:
            ans = anstmp
    if ans == 10**8:
        print(-1)
    else:
        print(ans)



if __name__=='__main__':
    main()

Submission status: Accepted

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

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

c=np.array(c)
a=np.array(a)

pat=2**n
ans=MAX
for i in range(pat):
    pat_i=bin(i)[2:].zfill(n)
    ai=np.array([0 for _ in range(m)])
    ansi=0

    for j in range(len(pat_i)):
        if(pat_i[j]=='1'):
            ansi+=c[j]
            ai+=a[j]

    if(min(ai)>=x):
        ans=min(ans,ansi)

if(ans!=MAX):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, m, x = ns()

    d = []
    for _ in range(n):
        d.append(na())

    ans = INF
    for i in range(2 ** n):
        score = [0 for _ in range(m + 1)]
        for j in range(n):
            if i >> j & 1:
                for k in range(m + 1):
                    score[k] += d[j][k]

        ## check
        flg = True
        for j in range(1, m + 1):
            if score[j] < x:
                flg = False
                break
        if flg:
            ans = min(ans, score[0])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n,m,x=map(int,input().split())
    L=[list(map(int,input().split())) for i in range(n)]
    val=10**10

    # bit全探索    
    # https://qiita.com/gogotealove/items/11f9e83218926211083a#%E4%BE%8B%E9%A1%8C-1
    for i in range(2 ** n):
        ans=[0]*m
        cnt=0
        for j in range(n):  # このループが一番のポイント
            if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
                cnt+=L[j][0]
                for k in range(1,m+1):
                    ans[k-1]+=L[j][k]
        flag=True
        for l in range(m):
            if ans[l]<x:
                flag=False
                break
        if flag==True:
            val=min(val,cnt)
        
    if val==10**10:
        print(-1)
    else:
        print(val)
    

    
resolve()

Submission status: Accepted

Solution code:
from itertools import product

N, M, X = map(int, input().split())
C, A = [], []
for _ in range(N):
    temp = [int(x) for x in input().split()]
    C.append(temp[0])
    A.append(temp[1:])

min_total = 10**10
for pattern in product([False, True], repeat=N):
    rikai = [0] * M
    total = 0
    for i, p in enumerate(pattern):
        if not p:
            continue
        for m in range(M):
            rikai[m] += A[i][m]
        total += C[i]

    if all(r >= X for r in rikai):
        min_total = min(total, min_total)

print(min_total if min_total < 10**10 else -1)

Submission status: Accepted

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

n = 1<<(N)
min_cost = 100000000
for one in range(n):
    tmp = [0]*M
    cost = 0
    for i in range(N):
        if (one>>i & 1)==1:
            cost+=CA[i][0]
            for j in range(M):
                tmp[j]+=CA[i][j+1]
    flag = True
    for i in range(M):
        if tmp[i]<X:
            flag=False
            break
    if flag:
        min_cost = min(min_cost, cost)
    
if min_cost == 100000000:
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
def main():
  N, M, X = map(int, input().split())
  ans = float('inf')
  table = []
  for i in range(N):
    table.append(list(map(int, input().split())))
                 
  for i in range(2 ** N):
    tmp = [0] * (M+1)
    for j in range(N):
        if ((i >> j) & 1):
            for k in range(M+1):
              tmp[k] += table[j][k]
    for l in range(1, len(tmp)):
      if tmp[l] < X:
        break
    else:
      if ans > tmp[0]:
        ans = tmp[0]
  if ans != float('inf'):
    print(ans)
  else:
    print(-1)  
    
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


def main():
    N, M, X_SUM = MI()
    C = [0] * N
    A = [None] * N

    for i in range(N):
        b = LI()
        C[i] = b[0]
        A[i] = b[1:]

    ans = 10**19
    for i in range(1, N+1):
        for select_idx in combinations(range(N), i):
            X = [0] * M
            price = 0
            for book_idx in select_idx:
                for x_idx in range(M):
                    X[x_idx] += A[book_idx][x_idx]
                price += C[book_idx]

            if all([x >= X_SUM for x in X]):
                ans = min(ans, price)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))

n, m, x = map(int, input().split())
ans = [0 for _ in range(m)]
a = []
minv = 1
for i in range(n):
    a.append(list(map(int, input().split())))
    minv += a[i][0]
maxv = minv
for i in range(2**n):
    ans = [0 for _ in range(m)]
    cnt = 0
    for j in range(n):
        if ((i>>j)&1):
            for k in range(m):
                ans[k] += a[j][k+1]
            cnt += a[j][0]
    ok = True
    for j in range(m):
        if ans[j] < x:
            ok = False
    if ok and cnt < minv: minv = cnt

print(minv) if minv != maxv else print(-1)

Submission status: Accepted

Solution code:
import numpy as np
n,m,x = map(int,input().split())
ca = np.array([list(map(int,input().split())) for i in range(n)])
# print(ca)
ans = 10**10
for i in range(2**(n+1)):
    abi = np.zeros(m+1)
    bin_str = format(i, '013b')
    # print(bin_str)
    for i in range(n):
        if bin_str[-i-1] == "1":
            abi += ca[i]
    if min(abi[1:]) >= x:
        ans = min(ans,abi[0])
        # print(bin_str,abi[0])
if ans == 10**10:
    print(-1)
else:
    print(int(ans))

Submission status: Accepted

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

ans=float("inf")
for i in range(2**N):
  bin=format(i, 'b')[::-1]
  #print(bin)
  l=0
  F=[0]*M
  for j,b in enumerate(bin):
    if b=="1":
      l+=L[j][0]
      for k in range(M):
        F[k]+=L[j][k+1]
  
  flag=1
  for k in range(M):
    if F[k]<X:
      flag=0
  if flag:
    ans=min(l,ans)
if ans==float("inf"):
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

ans = 10**10
for i in range(1<<n):
    use = []
    for bit in range(n):
        if i>>bit&1:
            use.append(bit)
    under = [0 for _ in range(m)]
    now = 0
    for j in use:
        for k,a in enumerate(data[j]):
            under[k] += a
        now += c[j]
    check = True
    for k in range(m):
        if under[k] < x:
            check = False
    if check:
        ans = min(ans, now)

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

Submission status: Accepted

Solution code:

n,m,x=map(int,input().split())
cost=[0]*n
l=[]
ans=-1
for i in range(n):
    l.append(list(map(int,input().split())))
for i in range(1<<n):
    skill=[0]*m
    cost=0
    bit=[(i>>j)&1 for j in range(n)]
    for j in range(n):
        if bit[j]==1:
            cost+=l[j][0]
            for k in range(m):
                skill[k]+=l[j][k+1]
    check=0
    for num in skill:
        if num<x:
            check=1
            break
    if check==0:
        if ans==-1:
            ans=cost
        else:
            ans=min(ans,cost)
print(ans)

Submission status: Accepted

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

m = 10**8
for i in range(1<<N):
    alg = [0]*M
    money = 0
    for j in range(N):
        if (i>>j)&1:
            money += CA[j][0]
            for k in range(M):
                alg[k] += CA[j][k+1]
    clear = True
    for k in range(M):
        clear = clear and alg[k]>=X
    if clear and money<m:
        m = money
if m == 10**8:
    m = -1
print(m)

Submission status: Accepted

Solution code:
n,m,x=(map(int,input().split()))
a=[]
ans=99999999999999999999999999
for i in range(n):
    a.append(list(map(int,input().split())))
for i in range(2**n+1):
    ta=0
    temp=[0]*m
    for j in range(n):
        if (i&(1<<j))!=0:
            ta+=a[j][0]
            for k in range(m):
                temp[k]+=a[j][k+1]
    flag=True
    # print(*temp)
    for k in range(m):
        if temp[k]>=x:
            continue
        flag=False
        break
    if flag:
        ans=min(ta,ans)
if ans==99999999999999999999999999:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m,x=map(int,readline().split())
    c=[]
    a=[]
    for i in range(n):
        ca=list(map(int,readline().split()))
        c.append(ca[0])
        a.append(ca[1:])
    
    min_res=float("inf")
    for i in range(1<<n):
        output=[]
        res=0
        rikaido=[0]*m
        for j in range(n):
            if(i>>j)&1:
                output.append(j)
        for j in output:
            res+=c[j]
            for k in range(m):
                rikaido[k]+=a[j][k]
        for k in range(m):
            if rikaido[k]<x:
                break
        else:
            min_res=min(res,min_res)

    if min_res==float("inf"):
        min_res=-1

    print(min_res)
if __name__=="__main__":
    main()

Submission status: Accepted

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

for i in range(2**N):
    b=bin(i)[2:].zfill(N)
    t_cost=0
    for j in range(N):
        t_cost+=A[j][0]*int(b[j])
        for m in range(M):
            S[i][m]+=A[j][m+1]*int(b[j])
    
    if min(S[i])>=X:
        cost.append(t_cost)

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

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
import numpy as np
setrecursionlimit(10 ** 7)

n,m,x = map(int,stdin.readline().rstrip().split())
a = []
li = []
mi = 10**9
for i in range(n):
    lin = list(map(int,stdin.readline().rstrip().split()))
    a.append(lin[0])
    li.append(lin[1:])

li = np.array(li)

for i in range(2**n):
    lis = np.zeros(m)
    mil = 0
    for j in range(n):
        if ((i >> j) & 1):
            lis += li[j]
            mil += a[j]
    flag = True
    for k in lis:
        if k < x:
            flag = False
    if flag:
        mi = min(mi,mil)

if mi == 10**9:
    print(-1)
    exit()

print(mi)

Submission status: Accepted

Solution code:
import itertools 
from itertools import combinations, chain 
  
def findsubsets(s, n): 
    return list(map(set, itertools.combinations(s, n))) 


arr=[]
n,m,x=list(map(int,input().split(" ")))
book=[]
for i in range(n):
	temp=list(map(int,input().split(" ")))
	book.append(temp)
s=[]
for i in range(0,n):
	s.append(i)
elig=[]
for i in range(1,n+1):
	temp=findsubsets(s,i)
	# print(temp)
	for j in range(len(temp)):
		sub=temp[j]
		algo=[0]*m
		cost=0
		for k in sub:
			b=book[k]
			cost+=b[0]
			for l in range(1,len(b)):
				algo[l-1]+=b[l]

		fl=0
		for k in range(m):
			if(algo[k]<x):
				fl=1
				break
		if(fl==0):
			elig.append(cost)
if(len(elig)==0):
	print(-1)
else:
	print(min(elig))

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M, X = rl()
C = []
As = []
for i in range(N):
	A = rl()
	C.append(A[0])
	As.append(A[1:])

def is_ok(b):
	sums = [0] * M
	for j in range(M):
		for i, v in enumerate(b):
			if v == 0: continue
			sums[j] += As[i][j]
		if sums[j] < X:
			return False
	return True

def cost(b):
	c = 0
	for i, v in enumerate(b):
		if v == 0: continue
		c += C[i]
	return c

import itertools
ans = float('inf')
for b in itertools.product([0, 1], repeat = N):
	if is_ok(b):
		ans = min(ans, cost(b))
if ans == float('inf'):
	print(-1)
else:
	print(ans)