Problem:


Score : 300 points

Problem

Takahashi, who is a novice in competitive programming, wants to learn M algorithms.
Initially, his understanding level of each of the M algorithms is 0.

Takahashi is visiting a bookstore, where he finds N books on algorithms.
The i-th book (1\leq i\leq N) is sold for C_i yen (the currency of Japan). If he buys and reads it, his understanding level of the j-th algorithm will increase by A_{i,j} for each j (1\leq j\leq M).
There is no other way to increase the understanding levels of the algorithms.

Takahashi's objective is to make his understanding levels of all the M algorithms X or higher. Determine whether this objective is achievable. If it is achievable, find the minimum amount of money needed to achieve it.

Constraints

All values in input are integers.

1\leq N, M\leq 12

1\leq X\leq 10^5

1\leq C_i \leq 10^5

0\leq A_{i, j} \leq 10^5

Input

Input is given from Standard Input in the following format:

N M X
C_1 A_{1,1} A_{1,2} \cdots A_{1,M}
C_2 A_{2,1} A_{2,2} \cdots A_{2,M}
\vdots
C_N A_{N,1} A_{N,2} \cdots A_{N,M}

Output

If the objective is not achievable, print -1; otherwise, print the minimum amount of money needed to achieve it.

Sample Input 1

3 3 10
60 2 2 4
70 8 7 9
50 2 3 9

Sample Output 1

120

Buying the second and third books makes his understanding levels of all the algorithms 10 or higher, at the minimum cost possible.

Sample Input 2

3 3 10
100 3 1 4
100 1 5 9
100 2 6 5

Sample Output 2

-1

Buying all the books is still not enough to make his understanding levels of all the algorithms 10 or higher.

Sample Input 3

8 5 22
100 3 7 5 3 1
164 4 5 2 7 8
334 7 2 7 2 9
234 4 7 2 8 2
541 5 4 3 3 6
235 4 8 6 9 7
394 3 6 1 6 2
872 8 4 3 7 2

Sample Output 3

1067



Sample input:
3 3 10
60 2 2 4
70 8 7 9
50 2 3 9


Sample output:
120

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1

        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])

    def print(self):
        for i in self.table:
            print(*i)


show_flg=False
show_flg=True
ans=0

n,m,x=LI()
c=[]
a=[]
for i in range(n):
    g=LI()
    c+=[g[0]]
    a+=[g[1:]]

ans=inf
for i in range(1<<n):
    tmp=[0]*m
    alt=0
    for j in range(n):
        if (i>>j)&1:
            alt+=c[j]
            for k in range(m):
                tmp[k]+=a[j][k]
            
    if all([y>=x for y in tmp]):
        if alt<ans:
            ans=alt
if ans==inf:
    ans=-1
print(ans)

Submission status: Accepted

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

ans = -1

def calc_score(data, score):
    for i in range(m):
        score[i] += data[i + 1]

def judge_score(score):
    for i in range(m):
        if score[i] < x:
            return False
    
    return True

for i in range(2 ** n):
    score = [0] * m
    price = 0
    for j in range(n):
        if i >> j & 1:
            calc_score(data[j], score)
            price += data[j][0]
    if judge_score(score):
        if ans == -1:
            ans = price
        else:
            ans = min(ans, price)

print(ans)

Submission status: Accepted

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

poss, best = 0, 10**9
for mask in range(2**n):
    lv = [0] * m
    cost = 0
    for bit in range(n):
        if (1 << bit) & mask:
            cost += ar[bit][0]
            for i in range(m):
                lv[i] += ar[bit][i+1]
    if sorted(lv)[0] >= x:
        poss = 1
        best = min(best, cost)
print(-1 if poss == 0 else best)

Submission status: Accepted

Solution code:
def main():
    N, M, X = [int(_n) for _n in input().split()]
    C = []
    books = []
    for i in range(N):
        l = [int(_n) for _n in input().split()]
        C.append(l[0])
        books.append(l[1:])
    ans = 10**8
    for i in range(0,2**N):
        res = [0]*M
        cost = 0
        a = 0
        # print(i)
        while True:
            if i % 2 == 1:
                cost += C[a]
                res = [res[i]+books[a][i] for i in range(M)]
            i//=2
            a+=1
            if i == 0:
                break
        # print(res)
        # print(cost)
        # print("-----")
        flag = True
        for j in range(M):
            if res[j] < X:
                # print("!!")
                flag = False
        if flag:
            ans = min(ans,cost)
    print(ans if ans != 10**8 else -1)

main()

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[]
for _ in range(n):
	aa=list(map(int,input().split()))
	a.append(aa)
ans=10**15
def two(x):
	return (n-len(bin(x)[2:]))*"0"+bin(x)[2:]
for i in range(2**n):
	r=two(i)
	b=[0]*m
	pre_ans=0
	for j in range(n):
		if r[j]=="1":
			pre_ans+=a[j][0]
			for k in range(m):
				b[k]+=a[j][k+1]
	f=1
	for j in range(m):
		if b[j]<x:
			f=0
			break
	if f:
		ans=min(ans,pre_ans)
print(ans if ans!=10**15 else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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


INF = 10 ** 18
ans = INF

for i in range(1, 2 ** N):
    cost = 0
    tmp = [0] * M
    for j in range(N):
        if (i >> j) & 1: #買う
            cost += lst[j][0]
            for k in range(M):
                tmp[k] += lst[j][k + 1]
    
    min_  = min(tmp)
    if min_ >= X:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
from itertools import combinations

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

cl = []
al = []
for _ in range(n):
    xl = list(map(int, input().split()))
    cl.append(xl[0])
    al.append(xl[1:])

res = 10**9
for r in range(n+1):
    for c in combinations(range(n), r=r):
        s = 0
        xl = [0]*m
        for i in c:
            s += cl[i]
            xl = [xl[j]+al[i][j] for j in range(m)]
        if all([q>=x for q in xl]):
            res = min(res,s)

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

Submission status: Accepted

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

ans = 10**10
for i in range(1<<N):
    und = [0]*M
    price = 0
    for j in range(N):
        if (i>>j)&1 == 0:
            price += book[j][0]
            for k in range(M):
                und[k] += book[j][k+1]
    b = True
    for num in und:
        if num < X:
            b = False
    if b:
        ans = min(ans,price)
        
if ans == 10**10:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
ca = [list(map(int, input().split())) for i in range(n)]
ans = 10 ** 18
for i in range(2**n):
  algo = [0] * m
  cost = 0
  for j in range(n):
    if (i >> j) & 1:
      book = ca[j]
      cost += book[0]
      for k,v in enumerate(book[1:]):
        algo[k] += v
  if all([j >= x for j in algo]):
    ans = min(ans,cost)
if ans == 10 ** 18:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def solve(N, i, C, A, M, X):
    tmp = [0] * M
    cost = 0
    for j in range(N):
        if (i >> j) % 2 == 1:
            cost += C[j]
            for k in range(M):
                tmp[k] += A[j][k]

    # print(tmp)
    if all(X <= t for t in tmp):
        return cost
    else:
        return float('inf')


def main():
    N, M, X = inpl()
    C = []
    A = []
    for _ in range(N):
        tmp = inpl()
        C.append(tmp[0])
        A.append(tmp[1:])

    ans = float("inf")
    for i in range(2**N):
        tmp = solve(N, i, C, A, M, X)
        if ans >= tmp:
            ans = tmp

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


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)]
INF = 10**12

def calc_cost(l):
    ret = 0
    rikai = [0 for _ in range(m)]
    for i in range(len(l)):
        c = l[i][0]
        ret += c
        a = l[i][1:]
        for j in range(m):
            rikai[j] += a[j]

    for i in range(m):
        if rikai[i] < x:
            ret = INF
    return ret

ans = INF
for i in range(2**n):
    l = []
    for j in range(n):
        if i >> j & 1:
            l.append(ca[j])
    ans = min(ans, calc_cost(l))
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

min_c=10000000
for i in range(2**n):
  u=[0 for j in range(m)]
  cost=0
  for j in range(n):
    if i & 2**j:
      cost+=c[j][0]
      for k in range(m):
        u[k]+=c[j][k+1]
  f=True
  if min_c<cost:
    continue
  for j in range(m):
    if u[j]<x:
      f=False
      break
  if f:
    min_c=cost
    
if min_c==10000000:
  print(-1)
else:
  print(min_c)

Submission status: Accepted

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

INF = 10**9
ans = INF
for i in range(1, 2**N):
    bk = [0 for _ in range(N)]
    tmp = i
    tmpi = 0
    while tmp > 0:
        if tmp&1 == 1:
            bk[tmpi] = 1
        tmp //= 2
        tmpi += 1
    und = [0 for _ in range(M+1)]
    cost = 0
    for i in range(N):
        if bk[i] == 1:
            cost += books[i][0]
            for j in range(1, M+1):
                und[j] += books[i][j]
    flag = True
    for j in range(1, M+1):
        if und[j] < X:
            flag = False
            break
    if flag:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
n,m,y = map(int,input().split())
inf = float('inf')
C = [0]*n
A = [[] for _ in range(n)]
for i in range(n):
    I = list(map(int,input().split()))
    C[i] = I[0]
    A[i] = I[1:]
ans = inf
for i in range(2**n):
    skill = [0]*m
    flag = 1
    cost = 0
    x = i
    j = 0
    while x > 0:
        if x&1:
            cost += C[j]
            for k in range(m):
                skill[k] += A[j][k]
        x = x >> 1
        j += 1
    for k in range(m):
        if skill[k] < y:
            flag = 0
    if flag:
        ans = min(ans,cost)
print(ans if ans != inf else -1)

Submission status: Accepted

Solution code:
#0や1のケースに注意
#index out of range

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n,m,x = map(int, input().split())
    c = []
    a = []
    for _ in range(n):
        s, *t = map(int, input().split())
        c.append(s)
        a.append(t)

    res = 10**10

    for i in range(1<<n):
        total = 0
        rikaido = [0]*m
        for j in range(n):
            if (i>>j) & 1:
                total += c[j]
                for k in range(m):
                    rikaido[k] += a[j][k]
        for k in range(m):
            if rikaido[k] < x:
                break
        else:
            res = min(res, total)
    
    if res == 10**10:
        print(-1)
    else:
        print(res)




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 = 10**9
for i in range(1, 2**N):
    tmp = 0
    S = [0]*M
    for j in range(N):
        if(i >> j) % 2 == 1:
            tmp += CA[j][0]
            for k in range(M):
                S[k] += CA[j][k+1]
        if min(S) >= X:
            ans = min(ans, tmp)
if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 


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


ans = 10**9
N = 1<<n
for mask in range(N):
    res = [0]*m
    cost = 0
    for i in range(n):
        if mask>>i&1:
            cost += ca[i][0]
            for j in range(1,m+1):
                res[j-1] += ca[i][j]
    if all(ri >= x for ri in res):
        ans = min(ans,cost)

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

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
c = []
a = []
for i in range(n):
  ci,*ai = map(int,input().split())
  c.append(ci)
  a.append(ai)

INF = float('inf')
ans = INF
for i in range(1<<n):
  r = [0 for _ in range(m)]
  p = 0
  for j in range(n):
    if (i>>j)&1 == 1:
      p += c[j]
      for k in range(m):
        r[k] += a[j][k]
  f = True
  for ri in r:
    if ri < x:
      f = False
      break
  #print(p,r,f)
  if f:
    ans = min(p,ans)
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
def main():
    n, m, x = map(int, input().split())
    ca = [list(map(int, input().split())) for _ in [0]*n]
    ans = 10**20
    for i in range(2**n):
        temp = [0]*m
        cost = 0
        for j in range(n):
            if i & 2**j:
                cost += ca[j][0]
                for k in range(m):
                    temp[k] += ca[j][k+1]
        for j in range(m):
            if temp[j] < x:
                break
        else:
            ans = min(ans, cost)
    if ans == 10**20:
        print(-1)
    else:
        print(ans)


main()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = []
A = []
for _ in range(N):
    c, *a = map(int, input().split())
    C.append(c)
    A.append(a)
res = 10**18
for i in range(2**N):
    D = [0 for _ in range(M)]
    cost = 0
    for j in range(N):
        if (i >> j) & 1:
            cost += C[j]
            for k in range(M):
                D[k] += A[j][k]
    for k in range(M):
        if D[k] < X:
            break
    else:
        res = min(res, cost)
print(res if res != 10**18 else -1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
ans = 10**10
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
for i in range(1<<N):
    li = [0]*M
    c = 0
    for j in range(N):
        if i>>j&1:
            c += A[j][0]
            for k in range(M):
                li[k] += A[j][k+1]
    f = True
    for x in li:
        if x < X:
            f = False
            break
    if f:
        ans = min(ans, c)
if ans != 10**10:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
N, M, X = map(int,input().split())
CA = np.array([tuple(map(int, input().split())) for _ in range(N)])
ans = 10**7
for i in itertools.product([0,1], repeat = N):
    cost = 0
    und = np.array([[0]*M])
    for x in range(N):
        if i[x]:
            cost += CA[x,0]
            und += CA[x,1::]
    if np.all(und >= X):
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,x = map(int,input().split())
data = [tuple(map(int,input().split())) for i in range(n)]
for bit in range(2**n):
  cost = 0
  tmp = [0] * m
  for i in range(n):
    if bit >> i & 1:
      for j in range(m):
        tmp[j] += data[i][j+1]
      cost += data[i][0]
  ok = 1
  for j in range(m):
    if tmp[j] < x: ok = 0
  if ok:
    mans = min(mans,cost)
  # print(cost,ok)
  # if cost == 1067:
  #   print(tmp)
print(mans if not mans == inf else -1)

Submission status: Accepted

Solution code:
from itertools import product

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

cost_min = 1e18
for idx in product([0,1], repeat = n):
    cost = 0
    t = [x] * m
    for j in range(n):
        if idx[j] == 1:
            for k in range(m):
                t[k] -= aa[j][k]
            cost += cc[j]
    if max(t) <= 0:
        if cost < cost_min:
            cost_min = cost
if cost_min == 1e18:
    print(-1)
else:
    print(cost_min)

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
data = []
for i in range(n):
    a = list(map(int, input().split()))
    data.append([a[0],a[1:]])
ans = 10**18
for i in range(pow(2,n)):
    i = list(("{:b}".format(i).zfill(n)))
    cost = 0
    learn = [0 for i in range(m)]
    for index,flag in enumerate(i):
        if int(flag):
            for j in range(m):
                learn[j] += data[index][1][j]
            cost += data[index][0]
    flag = True
    for j in range(m):
        if learn[j] < x:
            flag = False
    if flag:
        ans = min(ans, cost)
if ans == 10**18:
    print(-1)
else:
    print(ans)

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:
N, M, X = map(int, input().split())

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

inf = 10 ** 9 + 7
ans = inf
for bit in range(1 << N):
    tmp = [0] * M
    val = 0
    for i in range(N):
        if not (bit >> i & 1):
            continue

        val += C[i]
        for j in range(M):
            tmp[j] += A[i][j]
            
    # Check
    if all(v >= X for v in tmp):
        ans = min(ans, val)

print(ans if ans < inf else -1)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m, x = list(map(int, readline().split()))
    c = []
    a = []
    for i in range(n):
        temp = list(map(int, readline().split()))
        ctemp = temp[0]
        atemp = temp[1:]
        c.append(ctemp)
        a.append(atemp)

    ans = INF
    for bit in range(1 << n):
        money = 0
        learn = [0] * m
        for i in range(n):
            if bit >> i & 1:
                money += c[i]
                for j, le in enumerate(a[i]):
                    learn[j] += le

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

        if ok:
            ans = min(ans, money)

    if ans == INF:
        ans = -1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():

    N, M, X = map(int, input().split())
    B = [[0 for _ in range(M+1)]]
    for _ in range(N):
        A = list(map(int, input().split()))
        temp = []
        for b in B:
            tmp = [0 for _ in range(M+1)]
            for i in range(M+1):
                tmp[i] = b[i] + A[i]
            temp.append(tmp)
        B += temp

    minC = float('inf')
    for b in B:
        if all(u >= X for u in b[1:]):
            minC = min(minC, b[0])
    if minC == float('inf'):
        return -1
    return minC



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

Submission status: Accepted

Solution code:
import sys
from itertools import combinations as combi
input = sys.stdin.readline
N, M, X = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(N)]
res = float("inf")
for t in range(N + 1):
  for c in combi([x for x in range(N)], t):
    xs = [0] * M
    cc = 0
    for i in c:
      cc += a[i][0]
      for j in range(1, M + 1): xs[j - 1] += a[i][j]
    #print(xs, c)
    if min(xs) >= X: res = min(res, cc)
if res != float("inf"): print(res)
else: print(-1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
ca = [list(map(int, input().split())) for _ in range(N)]
ans = float('inf')
for i in range(2**N):
  bag = []
  und = [0]*M
  for j in range(N):
    if (i>>j)&1:
      bag += [j]
  tmp = 0
  for j in bag:
    tmp += ca[j][0]
    for k in range(1, M+1):
      und[k-1] += ca[j][k]
  flag = True
  for k in range(M):
    if und[k] < X:
      flag = False
      break
  if flag:
    ans = min(ans, tmp)

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

Submission status: Accepted

Solution code:
N,M,X=map(int,input().split())
CA=[list(map(int,input().split())) for i in range(N)]
from itertools import product
ans=10**9
for p in product((0,1),repeat=N):
    f=[0]*M
    c=0
    for i,x in enumerate(p):
        if x:
            c+=CA[i][0]
            for j in range(M):
                f[j]+=CA[i][j+1]
    a=1
    for j in range(M):
        if f[j]<X:
            a=0
    if a:
        ans=min(ans,c)
print(ans if ans<10**9 else -1)

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    N, M, X = map(int, input().split())
    lc = []
    la = []
    for _ in range(N):
        ca = list(map(int, input().split()))
        lc.append(ca[0])
        la.append(ca[1:])
    # print(N, M, X)
    # print(lc)
    # print(la)

    min_price = INF
    items = range(N)
    for i in range(1, len(items) + 1):
        for c in combinations(items, i):
            score = [0] * M
            price = 0
            for elem in c:
                price += lc[elem]
                for k in range(M):
                    score[k] += la[elem][k]
            # print(c, price, score, all(map(lambda x: x >= X, score)))
            if all(map(lambda x: x >= X, score)):
                if min_price > price:
                    min_price = price

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

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

ans = float("inf")
for pat in product([0, 1], repeat=n):
    sm = [0] * m
    cost = 0
    for i, bl in enumerate(pat):
        if bl:
            cost += ca[i][0]
            for j, e in enumerate(ca[i][1:]):
                sm[j] += e

    ok = True
    for e in sm:
        if e < x:
            ok = False

    if ok:
        ans = min(ans, cost)

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

print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int,input().split())
B = [list(map(int,input().split())) for k in range(N)]
ans = float("inf")
for k in range(2**N):
    p = 0
    t = [0]*M
    for d in range(N):
        if (k>>d)&1 == 1:
            p += B[d][0]
            for l in range(1,M+1):
                t[l-1] += B[d][l]
    if min(t) >= X:
        ans = min(ans,p)
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

def main():
    N, M, X = map(int, readline().rstrip().split())
    C, A = [], []
    for _ in range(N):
        c, *a = map(int, readline().rstrip().split())
        C.append(c)
        A.append(a)
    res = 10 ** 10
    for i in range(2**N):
        b = bin(i)[2:].zfill(N)
        buy_idx = [i for i, e in enumerate(b) if e == '1']
        flg = True
        for alg in range(M):
            if sum([A[j][alg] for j in buy_idx]) < X:
                flg = False
                break
        if flg:
            res = min(res, sum([C[j] for j in buy_idx]))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

oo = 10**10
ans = oo
for b in range(2**N):
  c = 0
  T = [0]*M
  for i in range(N):
    if b>>i&1:
      c += C[i]
      for j in range(M):
        T[j] += A[i][j]
  ok = True
  for i in range(M):
    if T[i]<X:
      ok = False
  if ok:
    ans = min(ans, c)

print(ans if ans<oo else -1)