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
from math import log2,floor,ceil,sqrt
# import bisect
sys.setrecursionlimit(10**5)
# from collections import deque

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

def backtrack(arr,cur,ans):
    if cur == n:
        alg = [0]*m
        cost  = 0
        for i in range(len(arr)):
            if arr[i] == 1:
                cost+=c[i]
                for j in range(m):
                    alg[j] += lis[i][j]
        flag = True
        for i in range(m):
            if alg[i] < k:
                flag = False
                break
        if flag :
            ans[0] = min(ans[0],cost)
        return
    arr[cur] = 0
    backtrack(arr,cur+1,ans)
    arr[cur] = 1
    backtrack(arr,cur+1,ans)
    arr[cur] = 0

n,m,k  = Ri()
c = [0]*n
lis = []
for i in range(n):
    temp = Ri()
    c[i] = temp[0]
    lis.append(temp[1:])

arr = [0]*n
ans = [INF]
backtrack(arr,0,ans)
if ans[0] == INF:
    print(-1)
else:
    print(ans[0])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from math import isinf
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, M, X = MI()
C = [0] * N
A = [list() for _ in range(N)]
for i in range(N):
    C[i], *A[i] = MI()

ans = INF
for bits in range(2 ** N):
    rikai = [0] * M
    cost = 0
    for i in range(N):
        if (bits >> i) & 1:
            cost += C[i]
            for j, a in enumerate(A[i]):
                rikai[j] += a
    if all(r >= X for r in rikai):
        ans = min(ans, cost)
if isinf(ans):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.read

n, m, k = map(int, input().split())
ca = np.array(read().split(), dtype=np.int64).reshape([n,m+1])

ans = 10**8

for i in range(2**n):
    b = np.array(list(format(i,'0'+str(n)+'b')), dtype=np.int64)
    d = ca[b == 1].sum(axis=0)
    if np.all(d[1:] >= k):
        ans = min(ans, d[0])

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

Submission status: Accepted

Solution code:
import numpy as np
N,M,X = map(int, input().split())
nd_list = np.ones(M)*X

next_list = []
for i in range(0,N):
    next_list.append(list(map(int, input().split())))
next_list = np.array(next_list)
min_tot = 10000000

def dfs(i,ab_list):
    global min_tot
    if i==N and np.all(ab_list[1:]>=nd_list):
        if min_tot > ab_list[0]:
            min_tot = ab_list[0]
        return True
    elif i ==N:
        return True

    dfs(i+1,ab_list)
    dfs(i+1,ab_list+next_list[i,:])


dfs(0,np.zeros(1+M))
if min_tot ==10000000:
    print(-1)
else:
    print(int(min_tot))

Submission status: Accepted

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

b = np.array(a)
total = []
for i in range(2**n):
    eff = np.array([0 for i in range(m)])
    money=0
    for j in range(n):
        if ((i >>j ) & 1):
            eff += b[j,1:]
            money+= b[j,0]
            if len(eff[eff>=x])==m:
                total.append(money)                
if len(total)==0:
    print(-1)
else:
    print(min(total))

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())))

study=[0]*m
ans=float("inf")
for i in range(2**n):
    study=[0]*m
    money=0
    for j in range(n):
        if (i>>j)%2 == 1:
            for k in range(m):
                study[k]+=a[j][k+1]
            money+=a[j][0]

    enough=True
    for k in range(m):
        if study[k]<x:
            enough=False
    if enough==True:
        ans=min(ans,money)

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

print(ans)

Submission status: Accepted

Solution code:
import copy
n, m, x = map( int, input().split() )
c = [ 0 ]
a = [[]]
for _ in range( n ):
    line = input().split()
    c = c + [ int( line[0] ) ]
    a = a + [ [ 0 ] + list( map( int, line[1:] ) ) ]

#print( n, m, x, c, a )

def search( understood, money, i ):
    if i > n:
        #print( understood )
        for j in range( 1, m+1 ):
            if understood[j] < x:
                return
        sum_money.append( money )
        return money
    else:
        search( understood, money, i+1 )
        next_understood = copy.deepcopy( understood )
        for j in range( 1, m + 1 ):
            next_understood[j] += a[i][j]
        next_money = money + c[i]
        search( next_understood, next_money, i+1 )

understood = [ 0 ] * ( m + 1 )
sum_money = []
search( understood, 0, 1 )
#sum_money.append( search( understood, 0, 1 ) )

try:
    print( min( sum_money ) )
except ValueError:
    print( "-1" )

Submission status: Accepted

Solution code:
from itertools import product
N,M,X = map(int,input().split())
C = []
A = []
for n in range(N):
    a = list(map(int,input().split()))
    C.append(a[0])
    A.append(a[1:])
INF = 10**9
ans = INF
for p in product([0,1], repeat=N):
    sm = [0] * M
    cost = 0
    for i in range(N):
        if p[i]:
            for m in range(M):
                sm[m] += A[i][m]
            
            cost += C[i] 
    #print (p,sm)
    if min(sm) >= X:
        ans = min(ans,cost)
if ans==INF:
    print (-1)
else:
    print (ans)

Submission status: Accepted

Solution code:
N, M, X = list(map(int, input().strip().split()))
A, C = [], []
max_price = N * 10**5 + 1
ans = max_price

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

def dfs(current, choice):
  global ans
  #print(f'{current=}, {choice=}')
  if current == N:
    b, c = judge(choice)
    if b:
      ans = min(ans, c)
  else:
    choice[current] = False
    dfs(current+1, choice)
    choice[current] = True
    dfs(current+1, choice)
    
def judge(choice):
  c = 0
  score_list = [0] * M
  for k, v in enumerate(choice):
    if v:
      c += C[k]
      for k2, v2 in enumerate(score_list):
        score_list[k2] = v2 + A[k][k2]  
  b = True
  for s in score_list:
    if s < X:
      b = False
      break
  return b, c

dfs(0, [False] * N)
if ans == max_price:
  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)]
b=list(range(n))
c=[0]*(m+1)
d=[]
for i in range(1,n+1):
    for v in itertools.combinations(b,i):
        for j in v:
            for k in range(m+1):
                c[k]+=a[j][k]
        d.append(c)
        c=[0]*(m+1)
e=[]
for i in range(len(d)):
    ok=0
    for j in range(1,len(d[i])):
        if d[i][j]>=x:
            ok+=1
    if ok==m:
        e.append(i)

if len(e)==0:
    print(-1)
else:
    ans=d[e[0]][0]
    for i in e:
        ans=min(ans,d[i][0])
    print(ans)

Submission status: Accepted

Solution code:
import itertools

def get_target_list(source):
    targets = []
    for size in range(1, len(source) + 1):
        for x in itertools.combinations(source, size):
            targets.append(x)
    return targets

paramN, paramM, paramX = list(map(lambda x: int(x), input().split(' ')))
targets = get_target_list([list(map(lambda x: int(x), input().split(' '))) for i in range(paramN)])

price_sum = 10000000000
for books in targets:
    ps = 0
    tmp = [0 for i in range(paramM)]
    for book in books:
        ps += book[0]
        for i1, x in enumerate(book[1:]):
            tmp[i1] += x
    if len(list(filter(lambda y: y < paramX, tmp))) == 0:
        price_sum = min(price_sum, ps)

if price_sum == 10000000000:
    print(-1)
else:
    print(price_sum)

Submission status: Accepted

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

book = [[None]*(m+1)]*n

for i in range(n):
    c = list(map(int, input().split()))
    book[i] = c
        

min_ans = float('inf')
for i in range(2 ** n):
    ans = 0
    rikai = [0]*m
    cost = 0

    for j in range(n):
        if((i >> j) & 1):
            p = book[j]
            for t in range(1,m+1):
                rikai[t-1] += p[t]
            cost += p[0]

    for j in range(m):
        if rikai[j] < x:
            ans = 1

    if ans == 0:
        min_ans = min(min_ans, cost)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools
d = defaultdict(int)

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

for i in range(N):
    for j in range(1, M + 1):
        d[j] += L[i][j]

for i in range(M):
    if (d[i + 1] < X):
        print('-1')
        exit()

n = []
for i in range(N):
    n.append(i)

p = []
for i in range(1, N + 1):
    p.append(itertools.combinations(n, i))

ans = []
for v in p:
    for i in v:
        d2 = defaultdict(int)
        for j in range(len(i)):
            for k in range(0, M + 1):
                if (k == 0):
                    d2[0] += L[i[j]][0]
                else:
                    d2[k] += L[i[j]][k]
        count = 0

        for p, q in d2.items():
            if(p == 0):
                continue
            else:
                if(q >= X):
                    count += 1

        if (count == len(d2) - 1):
            ans.append(d2[0])

print(min(ans))

Submission status: Accepted

Solution code:

n,m,x=map(int,input().split())
lst=[]
skl=[0]*m

money=0
moneylst=[]
flag=0
for i in range(n):
    lst.append(list(map(int,input().split())))
for i in range(2**n):
    s=bin(i)[2:].zfill(n)
    sindx=0
    skl=[0]*m
    money=0
    for j in s:
        j=int(j)
        if j==1:
            
            for k in range(m):
                skl[k]+=lst[sindx][k+1]
            money+=lst[sindx][0]
            

            if all(p>=x for p in skl):
                flag=1
                moneylst.append(money)
        sindx+=1

if flag==1:
    print(min(moneylst))
else:
    print('-1')

Submission status: Accepted

Solution code:
import itertools

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

for a in range(1, N + 1):
  for c in itertools.combinations(CA, a):
    C.append(list(c))

p = float('inf')

for c in C:
  tp = float('inf')
  t = [0] * (M + 1)
  for con in c:
    for i in range(M + 1):
      t[i] += con[i]
      flg = True
    for i in range(1, M + 1):
      if t[i] < X: flg = False
    if flg: p = min(p, t[0])
      
if p == float('inf'):
  print(-1)
else:
  print(p)

Submission status: Accepted

Solution code:
from copy import copy, deepcopy
from collections import Counter
from math import sqrt, floor, factorial
from itertools import permutations, combinations, combinations_with_replacement
from operator import mul
from functools import reduce
import bisect

MOD = 10**9 + 7
INF = float('inf')

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

C = [0]*N
A = [[0 for i in range(M)]for j in range(N)]

idxs = [i for i in range(N)]

ptn = []

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


for i in range(1 << len(idxs)):
    output = []
    for j in range(len(idxs)):
        if ((i >> j) & 1) == 1:
            output.append(idxs[j])
    ptn.append(output)

ans = -1
mans = 10000000000000

for p in ptn:
    cnt = [0]*M
    for i in p:
        for j in range(M):
            cnt[j] += A[i][j]

        if min(cnt) >= X:
            tmpans = 0
            for k in p:
                tmpans += C[k]
            if tmpans < mans:
                ans = p
                mans = tmpans

if mans == 10000000000000:
    print(-1)
else:
    print(mans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,m,x=map(int,input().split())
    C=[0]*n
    A=[0]*n
    for i in range(n):
        c,*a=map(int,input().split())
        C[i]=c
        A[i]=a
    ans=-1
    for i in range(2**n):
        flag=True
        for j in range(m):
            u=0
            for d in range(n):
                u+=A[d][j]*(i>>d&1)
            if u<x:
                flag=False
        if flag:
            price=0
            for d in range(n):
                price+=C[d]*(i>>d&1)
            if ans==-1 or ans>price:
                ans=price
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# sys.stdin = open('input.txt')

import itertools

def add_lists(a, b):
    result = [0 for i in range(len(a))]
    for i in range(len(a)):
        result[i] = a[i] + b[i]
    return result

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

INF = float('inf')
ans = INF

for flags in itertools.product([0,1], repeat=n):
    tot = [0 for i in range(m)]
    now = 0
    for i in range(len(flags)):
        if flags[i] == 1:
            tot = add_lists(tot, a[i])
            now += c[i]
    flag = True
    for i in tot:
        if i < x:
            flag = False
    if flag:
        ans = min(ans, now)

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

Submission status: Accepted

Solution code:
import numpy as np

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


min=-1
for nnn in range(2**n):
    index=[]
    a=nnn
    for i in range(n):
        index.append(a%2)
        a//=2

    money=0
    xs=np.zeros(m)
    for i in range(n):
        if index[i]==1:
            money+=lis[i][0]
            xs+=np.array(lis[i][1:])
    if np.amin(xs)>=x:
        if min==-1:
            min=money
        elif min>money:
            min=money

print(min)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


class Solver(object):

    def solve(self):

        def checker(current, X):
            for idx, value in enumerate(current):
                if idx == 0:
                    continue
                elif value < X:
                    return False
            return True

        def add_list(a, b):
            for i in range(len(a)):
                a[i] += b[i]
            return a

        N, M, X = [int(i) for i in input().split()]
        book_list = [[int(i) for i in input().split()] for _ in range(N)]
        init = [0] * (M + 1)
        ans = []
        for i in range(1 << N):  # 2^N のパターンを全探索
            cur = [0] * (M + 1)
            for j in range(N):  # bitの長さを取る
                if (i >> j) & 1:
                    cur = add_list(cur, book_list[j])
            if checker(cur, X):
                ans.append(cur[0])

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


def main():
    solver = Solver()
    print(solver.solve())


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import copy

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

Clist = []

for i in range(N):
    Clist.append(list(map(int, input().split())))

anslist = []


def dfs(index, tmplist):
    if index >= N:
        anslist.append(copy.copy(tmplist))
        return

    s = list(tmplist)

    for i in range(M+1):
        s[i] += Clist[index][i]

    dfs(index+1, s)
    dfs(index+1, tmplist)


dfs(0, [0]*(M+1))

ans = -1

for al in anslist:
    flg = True
    for a in range(1, M+1):
        if al[a] < X:
            flg = False

    if flg:
        if ans == -1:
            ans = al[0]
        else:
            ans = min(ans, al[0])


print(ans)

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
l = []
for i in range(n):
    a = list(map(int, input().split()))
    l.append(a)
ans = []
for i in range(2**len(l)):
    l2 = []
    for j in range(len(l)):
        if (i >> j) & 1 == 1:
            l2.append(l[j])
    #print(l2)
    s = [0] * (m + 1)
    for j in range(len(l2)):
        for k in range(m + 1):
            s[k] += l2[j][k]
    ans.append(s)
min = float("INF")
for i in range(2 ** len(l)):
    c = 0
    for j in range(1, m + 1):
        if ans[i][j] >= x:
            c += 1
    if c == m and min > ans[i][0]:
        min = ans[i][0]
print(-1 if min == float("INF") else min)

Submission status: Accepted

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

ans = 100000000
l = 0
for i in range(2**n):
    ab = [0]*m
    kari = 0
    for j in range(n):
        if (i >> j) & 1:
            ab = [x + y for (x, y) in zip(ab, a[j])]
            kari += c[j]
    if all([z >= x for z in ab]):
        ans = min(ans,kari)
        l += 1

if l == 0:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
def mips():
    return map(int,input().split())
def msps():
    return map(str,input().split())

import sys
import itertools
N,M,X = mips()
know = dict()
price = [[] for _ in range(N)]
L = []
C = []
for i in range(M):
    know[i] = 0
for i in range(N):
    L.append([i for i in mips()])
    C.append(L[i][0])
    L[i].remove(L[i][0])
Money = []
paid = 0 
K = []
No = 0
P = []
Q = [i for i in range(N)]
for i in range(N+1):
    P.append(list(itertools.combinations(Q,i)))
for k in range(N+1):
    for el in P[k]:
        for book in el:
            K = L[book] 
            paid += C[book]
            for i in range(M):
                know[i] += K[i]
        for i in range(M):
            if know[i] < X:
                No = 1
                break
        if No == 0:
            Money.append(paid)
        paid = 0
        No = 0
        for i in range(M):
            know[i] = 0
if Money == []:
    print("-1")
else:
    print(min(Money))

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
ans=1e15
for f in range(1<<n):
  p,c=[0]*m,0
  for i in range(n):
    if f%2:
      p=list(map(lambda x,y:x+y,p,a[i][1:]))
      c+=a[i][0]
    f//=2
  if all(p[i]>=x for i in range(m)):
    ans=min(ans,c)
print(-1 if ans>=1e15 else ans)

Submission status: Accepted

Solution code:

inf = pow(10, 9) + 7

def solve(m, x, bag):

    p = [0]*(m+1)

    for i in range(len(bag)):
        for j in range(m+1):
            p[j] += bag[i][j]

    for i in range(1,m+1):
        if p[i] < x:
            return inf
    else:
        return p[0]

if __name__ == '__main__':

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

    mini = inf

    for i in range(2**n):
        bag = []
        #print("p{} : ".format(i), end="")

        for j in range(n):
            if((i >> j) & 1):
                bag.append(l[j])
        #print(bag)
        r = solve(m, x, bag)
        if mini > r:
            mini = r

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

Submission status: Accepted

Solution code:
import sys
N,M,X=map(int, sys.stdin.readline().split())
C=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

ans=float("inf")

for n in range(2**N):
    L=[0 for _ in range(M+1)]
    price=0
    for i in range(N):
        if n>>i&1==1:
            for j,x in enumerate(C[i]):
                if j==0:
                    price+=x
                else:
                    L[j]+=x    
        if X<=min(L[1:]):
            ans=min(ans,price)
if ans==float("inf"):
    print -1
else:
    print ans

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
            
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################



n,m,x = list(map(int, input().split()))
costlist = []
info = []
for i in range(n):
    temp = list(map(int, input().split()))
    costlist.append(temp[0])
    info.append(temp[1:])

ans = 10**9
for i in range(2**n):
    bits = ValueToBits(i,n)
    sums = [0 for j in range(m)]
    costs = 0
    for j in range(n):
        if (bits[j]==1):
            costs+= costlist[j]
            for l in range(m):
                sums[l] += info[j][l]
    ok = 1
    for l in range(m):
        if(sums[l] < x):
            ok = 0
    if(ok == 1):
        ans = min(ans, costs)


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

Submission status: Accepted

Solution code:
from itertools import combinations

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

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

s = float('inf')
r = False

for i in range(1, N + 1):
    C = combinations(range(0, N), i)
    for c in C:
        _s = 0
        t = [0 for _ in range(M)]
        for _c in c:
            _s += L[_c][0]
            for k in range(M):
                t[k] += L[_c][k + 1]
        _r = True
        for _t in t:
            if _t < X:
                _r = False
                break
        if _r and _s < s:
            r = True
            s = _s
if r:
    print(s)
else:
    print(-1)

Submission status: Accepted

Solution code:
from itertools import combinations

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

# print(cost_lists)

min_cost = 10**9
unst_flag = False

for i in range(1, n+1):
    combi_lists = list(combinations(range(n), i))

    for combi_list in combi_lists:
        tmp_list = list()
        for j in range(1,m+1):
            tmp_unst = 0
            for k in combi_list:
                tmp_unst += cost_lists[k][j]

            tmp_list.append(tmp_unst)
        
        if min(tmp_list) >= x:
            tmp_cost = 0
            for k in combi_list:
                tmp_cost += cost_lists[k][0]

            min_cost = min(min_cost, tmp_cost)
            unst_flag = True

if unst_flag:
    print(min_cost)
else:
    print(-1)

Submission status: Accepted

Solution code:
# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n, m, x = map(int, input().split())
    c = []
    a = []
    cost_list = []
    for i in range(n):
        tmp = list(map(int, input().split()))
        c.append(tmp[0])
        a.append(tmp[1: m + 1])
    for i in range(1, n + 1):
        sets = list(itertools.combinations(range(1, n+1), i))
        # print(sets)
        for j in sets:
            cost = 0
            a_score = [0]*m
            for k in j:
                cost += c[k - 1]
                for l in range(m):
                    a_score[l] += a[k - 1][l]
            flg = 0
            for k in a_score:
                if k < x:
                    flg = 1
            if flg == 0:
                cost_list.append(cost)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

class A:

    def solve(self):
        s1 = input()
        s2 = input()
        print("Yes" if s1 == s2[:-1] else "No")

class B:

    def solve(self):
        A, B, C, K = tuple(map(int, input().split(" ")))
        sum = min(A, K)
        K -= A
        K -= B
        sum -= max(min(K, C), 0)
        print(sum)

class C:

    def solve(self):
        n, m, t = tuple(map(int, input().split(" ")))
        costs = []
        matrix = [[0 for x in range(m)] for y in range(n)]

        for i in range(n):
            line = [int(x) for x in input().split(" ")]
            costs.append(line[0])
            for j in range(len(line[1:])):
                matrix[i][j] = line[j+1]

        end = 2**n
        min_cost = sys.maxsize
        for i in range(end):
            binary = [int(x) for x in ("{:032b}".format(i))[-n:]]
            skills = list(map(lambda x: x[1], filter(lambda x: x[0] == 1, zip(binary, matrix))))
            acc = [0 for x in range(m)]

            for x in skills:
                acc = [x + y for x,y in zip(acc, x)]

            if all(map(lambda x: x >= t, acc)):
                ccost = sum(map(lambda x: x[1], filter(lambda x: x[0] == 1, zip(binary, costs))))
                if min_cost > ccost:
                    min_cost = ccost

        print(min_cost if min_cost != sys.maxsize else -1)

C().solve()

Submission status: Accepted

Solution code:
from itertools import combinations

def Main(N, M, X, C, A):
    inds = list(range(N))
    ind_subset = []
    for i in range(1, N+1):
        for c in combinations(inds, i):
            ind_subset.append(c)
    ans = []
    for e in ind_subset:
        c = 0
        a = [0]*M
        for j in e:
            c += C[j]
            a = [a[k]+A[j][k] for k in range(M)]
        if min(a) >= X:
            ans.append(c)
    if len(ans) == 0:
        return -1
    else:
        return min(ans)      
    
def main():
    N, M, X = map(int, input().split())
    B = []
    C = []
    A = []
    for i in range(N):
        B = list(map(int, input().split()))
        c = B[0]
        a = B[1:]
        C.append(c)
        A.append(a)
    print(Main(N, M, X, C, A))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

C_A_list = []
for i in range(N):
    C_A = [int(x) for x in input().split()]
    C_A_list.append(C_A)

all_list = []
for i in range(1, len(C_A_list)+1):
    for j in itertools.combinations(C_A_list, i):
        all_list.append(list(j))

cost_list = []
for comb in all_list:
    comb_ = np.array(comb)
    if [i >= X for i in sum(comb_)[1:]] == [True] * M :
        cost_list.append(sum(comb_)[0])

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

Submission status: Accepted

Solution code:
def avi_chk(X,avi_list):
    for a in avi_list:
        if a<X:
            return False
    return True

def t1():
    import numpy as np

    N,M,X=map(int,input().split())
    C_list=[]
    avility=[]
    for i in range(N):
        c=list(map(int,input().split()))

        avility.append(c)
        
    min_v=-1
    for i in range(2**N):
        v=0
        now_avi=np.zeros(M)
        for j in range(N):
            if((i>>j)&1):
                now_avi+=avility[j][1::]
                v+=avility[j][0]
        if avi_chk(X,now_avi):
            if min_v==-1:
                min_v=v
            elif min_v>v:
                min_v=v
    print(min_v)

            
        
                

      
if __name__ == '__main__':
    t1()

Submission status: Accepted

Solution code:
N,M,X = map(int, input().split())
book = []
hm = []
total_price = []
for i in range(N):
  one = list(map(int, input().split()))
  hm.append(one[0])
  one.pop(0)
  book.append(one)

for i in range(2 ** N):
  sougaku = 0
  point = [0] * M
  for j in range(N):
    if ((i >> j) & 1):
      point = [x + y for (x, y) in zip(point,book[j])]
      sougaku += hm[j]
  if min(point) >= X:
    total_price.append(sougaku)

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