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:
from itertools import product

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

bit = [0, 1]
ans = float('inf')
for l in product(bit, repeat=n):
    a = [0] * m
    cnt = 0
    for k, i in enumerate(l):
        if i == 1:
            cnt += ca[k][0]
            for i in range(1, m + 1):
                a[i - 1] += ca[k][i]
    if all(i >= x for i in a):
        ans = min(ans, cnt)

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import combinations, product
#import bisect# lower_bound etc
import numpy as np
def run():
    N,M,X = map(int, sysread().split())
    C = []
    A = []
    for _ in range(N):
        c, *a = map(int, sysread().split())
        C.append(c)
        A.append(a)
    A = np.array(A)
    C = np.array(C)
    val = float('inf')
    for buy in product((0,1), repeat=N):
        buy = np.array(list(buy))
        cost = (C * buy).sum()
        prog = (A.T * buy).sum(axis=1)
        if np.all(prog >= X):
            val = min(val, cost)
    if val == float('inf'):
        print(-1)
        return None
    print(val)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import itertools

N,M,X = map(int, raw_input().split())
Data = [map(int, raw_input().split()) for _ in range(N)]
C = [itertools.combinations(Data, i) for i in range(N+1)]
ans = -1
for c in itertools.chain.from_iterable(C):
    # print list(c)
    T = [0]*(M+1)
    for a in c:
        for i,b in enumerate(a):
            T[i] += b
    # print T
    ok = True
    for t in T[1:]:
        if t < X:
            ok = False
            break

    if ok:
        price = T[0]
        # print price
        if ans == -1:
            ans = 100000000
        ans = min(ans, price)

print ans

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(n)]
ans = 10**18

for i in range(2 ** n):
    check = [0] * n

    for j in range(n):
        if ((i >> j) & 1):
            check[n - 1 - j] = 1

    total = 0
    skill = [0] * m
    for k in range(n):
        if check[k] == 0:
            continue
        total += li[k][0]

        for l in range(m):
            skill[l] += li[k][l+1]

    skill.sort()
    if skill[0] >= x:
        ans = min(ans,total)

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

Submission status: Accepted

Solution code:
import numpy as np
from itertools import product
from sys import maxsize

n, m, x = map(int, input().split())
c = []
a = np.empty((n, m), dtype='i8')
for i in range(n):
    ipt = list(map(int, input().split()))
    c.append(ipt[0])
    a[i] = ipt[1:]

can = False
res = maxsize
for pt in product(range(2), repeat=n):
    understanding = np.zeros(m, dtype='i8')
    price = 0
    for i, b in enumerate(pt):
        if b:
            understanding += a[i]
            price += c[i]

    if np.all(understanding >= x):
        can = True
        if price < res:
            res = price

print(res) if can else print(-1)

Submission status: Accepted

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

# from fractions import gcd
from math import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

import copy
N, M, X = [int(_) for _ in input().split()]
CA = [[int(_) for _ in input().split()] for i in range(N)]

ret = []

def dfs(index, rikaido, cost):
    
    global ret
    rikaido = [rikai + rikaido[i] for i, rikai in enumerate(CA[index][1:])]
    cost += CA[index][0]

    if all([i >= X for i in rikaido]):
        ret += [cost]
        return
    
    for i in range(index+1, N):
        dfs(i, copy.copy(rikaido), cost)

for i in range(N):
    dfs(i, [0] * M, 0)

if not ret:
    print(-1)
else:
    print(min(ret))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# from collections import Counter
# from functools import *
import itertools  
import numpy as np
def LI():
    return (map(int,input().split()))

n,m,x=LI()
c=[]
a=[]
for i in range(n):
    ct,*at=LI()
    c.append(ct)
    a.append(at)
    
a=np.array(a)

ans=10**15
rrr=list(itertools.product((0,1),repeat=n))
# print(rrr)
for i in rrr:
    tmp=np.array([0]*m)
    cost=0
    for j,k in enumerate(i):
        if k==1:
            tmp+=a[j]
            cost+=c[j]
        if all(tmp>=x):
            ans=min(ans,cost)
if ans==10**15:
    ans=-1
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import itertools


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

L = [0, 1]
num = N
bit_list = list(itertools.product(L, repeat=num))

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

if __name__ == "__main__":

    min_cost = float('inf')
    for bit in bit_list:
        cost = 0
        understand = [0 for _ in range(M)]
        for i in range(N):
            if bit[i] == 1:
                cost += C[i]
                for j in range(M):
                    understand[j] += A[i][j]
        
        clear = True
        for u in understand:
            if u < X:
                clear = False
                break
        
        if clear and cost < min_cost:
            min_cost = cost
    
    if min_cost == float('inf'):
        print(-1)
    else:
        print(min_cost)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N, M, X = map(int, input().split())
    C = [0] * N
    A = []
    for n in range(N):
        s = list(map(int, input().split()))
        C[n] = s[0]
        A.append(s[1:])
    
    res = INF
    for bit in range(2**N):
        tmp = 0
        P = [0] * M
        for n in range(N):
            if (bit >> n) & 1:
                tmp += C[n]
                for m in range(M):
                    P[m] += A[n][m]
        flg = True
        for m in range(M):
            if P[m] < X:
                flg = False
        if flg:
            res = min(res, tmp)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,x = map(int, input().split())
C = []
A = []
ans = 10**9
for i in range(n):
  AC = list(map(int,input().split()))
  C.append(AC.pop(0))
  A.append(AC)

for i in range(2**n):
  cost = 0
  crit = [0]*m
  for j in range(n):
    if (i>>j)& 1:#use
      for k in range(m):
        crit[k] += A[j][k]
      cost += C[j]
  if min(crit) >= x:
    ans = min(ans, cost)
  #print(crit, cost)
if ans == 10**9:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
import itertools
[N,M,X] = list(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:])

TF = [0,1]
L = list(itertools.product(TF, repeat=N))

out = float('inf')
for K in L:
    Cost = 0
    ML = [0]*M
    for i in range(N):
        if K[i]==1:
            for j in range(M):
                ML[j]+=A[i][j]
            Cost+=C[i]
    flag = 1
    for j in range(M):
        if ML[j]<X:
            flag = 0
    if flag==1:
        if Cost < out:
            out = Cost

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

Submission status: Accepted

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


import itertools
L = [0, 1] #生成する数字
num = N #生成するビット数
bl = list(itertools.product([0, 1], repeat=num))

acost = 10**9

for i in range(len(bl)):
    tcost = 0
    tskill = [0]*M
    t = bl[i]
    for j in range(N):
        if t[j] == 1:
            tcost += C[j][0]
            for k in range(M):
                tskill[k] += C[j][k+1]
    if min(tskill) >= X:
        if acost > tcost:
            acost = tcost
            
if acost == 10**9:
    print(-1)
else:
    print(acost)

Submission status: Accepted

Solution code:
def make_smpl(m):
    if m == 0:
        return [[]]
    tmp = make_smpl(m - 1)
    result = []
    for l in tmp:
        result += [[0] + list(l), [1] + list(l)]
    return result


def calc(N, M, X, B):
    result = sum([b[0] for b in B])
    p = False
    for smpl in make_smpl(N):
        a = [0] * (M + 1)
        for i in range(N):
            if smpl[i] == 1:
                for j in range(M + 1):
                    a[j] += B[i][j]
        q = True
        for j in range(M):
            if a[j + 1] < X:
                q = False
                break
        if q:
            result = min(result, a[0])
            p = True
    return result if p else -1
    

(N, M, X) = tuple([int(s) for s in input().split()])
B = [[int(s) for s in input().split()] for _ in range(N)]
print(calc(N, M, X, B))

Submission status: Accepted

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

minsum=0
booklist=[]
for i in range(n):
    booklist.append(list(map(int,input().split())))
    minsum+=booklist[i][0]
minsum+=1
org=minsum
for i in range(2**n):
    masterlist=[0 for _ in range(m+1)]
    for j in range(n):
        if ((i>>j) & 1):
            for k in range(m+1):
                masterlist[k]=masterlist[k]+booklist[j][k]
    flag = True
    for l in range(1,m+1):
        if masterlist[l] < x:
            flag = False

    if flag:
        if masterlist[0] < minsum:
            minsum=masterlist[0]

if minsum == org:
    print(-1)
else:
    print(minsum)

Submission status: Accepted

Solution code:
import numpy as np

n, m, x = map(int, input().strip().split())
cs = []
aij = []
for _ in range(n):
    row = list(map(int, input().strip().split()))
    cs.append(row[0])
    aij.append(row[1:])


def check(bits, n, m, x):
    cost = 0
    skills = np.zeros(m, dtype=np.int)
    for i in range(n):
        bit = bits & (2 ** i)
        if bit:
            cost += cs[i]
            skills += aij[i]

    if np.all(skills >= x):
        return cost
    else:
        return False


min_cost = 1e30


for bits in range(2**n):
    result = check(bits, n, m, x)
    if not result:
        continue

    min_cost = min(min_cost, result)


if min_cost == 1e30:
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, M, X = lr()
    C = []
    A = []
    for i in range(N):
        CA = lr()
        C.append(CA[0])
        A.append(CA[1:])
    ans = float('inf')
    for i in range((1<<N)+1):
        rikai = [0]*M
        d = [0]*M
        tmp = 0
        for j in range(N):
            if (i>>j)&1:
                tmp += C[j]
                for k in range(M):
                    if d[k] == 1:
                        continue
                    rikai[k] += A[j][k]
                    if rikai[k] >= X:
                        d[k] = 1
        if d == [1]*M:
            ans = min(ans, tmp)
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)
resolve()

Submission status: Accepted

Solution code:
def f(i):
    global ans
    if i == n:
        t = []
        cost = 0
        for j in range(n):
            if s[j] == 1:
                t.append(j)
        for j in range(1, m + 1):
            c = 0
            for k in t:
                c += a[k][j]
            if not c >= x:
                return
        for j in t:
            cost += a[j][0]
        ans = min(ans, cost)
        return
    f(i + 1)
    s[i] = 1
    f(i + 1)
    s[i] = 0
 
n, m, x = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
s = [0] * n
ans = pow(10, 10)
f(0)
print(ans if not ans == pow(10, 10) else -1)

Submission status: Accepted

Solution code:
#N = int(input())
#J,K = map(int,input().split())
#A = list(map(int(input().split())))
#A = [list(map(int(input().split()))) for _ in range(N)]
#for i in range():

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

for i in range(2**N):
    A = []
    c = 0
    B = [0]*M
    for j in range(N):
        if ((i >> j) & 1):
            A.append(j)
    for k in A:
        for l in range(M):
            B[l] += C[k][l+1]
        c += C[k][0]
    if min(B) >= X:
        ans = min(ans,c)
if ans != 10**10:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import numpy as np

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


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


def cost(buy):
    return np.dot(buy, c)


def learnable(buy):
    return np.min(np.dot(buy, a)) >= x


answer = False, 10 ** 8
for bit in range(2 ** n):
    buy = np.array([int(i) for i in bin(bit)[2:].zfill(n)])
    if learnable(buy):
        answer = True, min(answer[1], cost(buy))


if answer[0]:
    print(answer[1])
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
    from itertools import product
    n,m,x = map(int,input().split())
    A = []
    for i in range(n):
        a = list(map(int,input().split()))
        A.append(a)
    P = product([0,1], repeat=n)
    ans = float('inf')
    for p in P:
        a = [0 for i in range(m)]
        M = 0
        for i in range(len(p)):
            if p[i]==1:
                M += A[i][0]
                for j in range(1,len(A[i])):
                    a[j-1]+=A[i][j]
        flg = 0
        for i in range(len(a)):
            if a[i]<x:
                flg = 1
                break
        if M<ans and flg==0:
            ans = M
    if ans == float('inf'):
        print(-1)
    else:
        print(ans)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def abc167_c():
    import numpy as np
    N, M, X = map(int, input().split())
    Cost = [0] * N
    Query = np.zeros((N, M), dtype=int)
    for i in range(N):
        row = list(map(int, input().split()))
        Cost[i] = row[0]
        Query[i] = row[1:]
    ans = 10**9

    from itertools import product
    for v in product(range(2), repeat=N):
        score = np.zeros(M, dtype=int)
        co = 0
        for i in range(N):
            if v[i] == 0: continue
            score += Query[i]
            co += Cost[i]
        if X <= np.min(score):
            ans = min(co, ans)
    if ans < 10**9: print(ans)
    else: print(-1)

abc167_c()

Submission status: Accepted

Solution code:
import numpy as np
if __name__ == "__main__":
    N, M, X = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(N)]
    ans = -1
    for i in range(2 ** N):
        rikai = np.zeros(M)
        cost = 0
        for j in range(N):
            if ((i>>j) & 1):
                cost += D[j][0]
                #print(rikai)
                rikai = rikai + np.array(D[j])[1:]
        #print(rikai)
        #print(cost)
        if np.all(X <= rikai):
            #print('Yes')
            if ans == -1:
                ans = cost
            else:
                ans = min(ans, cost)
    print(ans)

Submission status: Accepted

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


def read():
    N, M, X = map(int, input().strip().split())
    C, A = [], []
    for i in range(N):
        line = list(map(int, input().strip().split()))
        C.append(line[0])
        A.append(line[1:])
    return N, M, X, C, A


def solve(N, M, X, C, A, INF = 10**8):
    stats = [0 for i in range(M)]
    
    def dfs(n):
        if all([s >= X for s in stats]):
            return 0
        if n >= N:
            return INF
        
        c1 = dfs(n+1)
        for i in range(M):
            stats[i] += A[n][i]
        c2 = dfs(n+1) + C[n]
        for i in range(M):
            stats[i] -= A[n][i]
        return min(c1, c2)

    c = dfs(0)
    return c if c < INF else -1


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

ans = 10000000000000

hon = []


def dfs(cost, now, nextt):
    global N, M, X, ans, hon
    okcnt = 0
    for i in range(M):
        if now[i] >= X:
            okcnt += 1

    if okcnt == M:
        ans = min(cost, ans)

    if nextt >= N:
        return

    temp = now.copy()
    temp2 = now.copy()
    for j in range(M):
        temp[j] += hon[nextt][j + 1]

    dfs(cost + hon[nextt][0], temp, nextt + 1)
    dfs(cost, temp2, nextt + 1)


for i in range(N):
    c = list(map(int, input().split()))

    hon.append(c)

li = [0] * M

dfs(0, li, 0)

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

Submission status: Accepted

Solution code:
N,M,x = [int(x) for x in input().split()]
l = []
und = [0]*M
ans = 10**7
for i in range(N):
    uke = [int(x) for x in input().split()]
    l.append(uke)
#bit全探索
for i in range(2**N):
    und = [0]*(M)
    money = 0
    for j in range(N):
        if ((i >> j)&1):
            money += l[j][0]
            for k in range(M):
                und[k] += l[j][k+1]
    if min(und) >= x:
        ans = min(ans,money)
if ans == 10**7:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest


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

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

    for i in range(2 ** n):
        cost = 0
        skills = [0] * m
        for j in range(n):
            if ((i >> j) & 1):
                cost += ca[j][0]
                for num, s in enumerate(ca[j][1:]):
                    skills[num] += s

        if all([sk >= x for sk in skills]):
            cost_list.append(cost)

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


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 3 10
60 2 2 4
70 8 7 9
50 2 3 9"""
        output = """120"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """3 3 10
100 3 1 4
100 1 5 9
100 2 6 5"""
        output = """-1"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """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"""
        output = """1067"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:

def ma():
    return map(int,input().split())
y="Yes"
t="No"
n,m,x=ma()
CA=[list(ma()) for _ in range(n)]

ans=10**9
for i in range(2**n):
    temp=0
    dp=[0]*m
    base=0
    
    while i>>base:
        if (i>>base)&1==1:
            #print(t,i)
            temp+=CA[base][0]
            for j in range(m):
                dp[j]+=CA[base][j+1]
        base+=1
    
    for j in range(m):
        if dp[j]<x:
            break
    else:
        ans=min(ans,temp)
if ans==10**9:
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

c, *aa = zip(*[tuple(map(int, input().split())) for _ in range(n)])
ans = float("inf")

for i in range(2 ** n):
    cnt = 0
    a = [0] * m
    items = [j for j in range(n) if (i >> j) & 1]

    for item in items:
        cnt += c[item]
        for k in range(m):
            a[k] += aa[k][item]
    
    if min(a) >= x: ans = min(cnt, ans)

print(-1 if ans == float("inf") else ans)

Submission status: Accepted

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

for bit in range(1<<N):
    r = [0] * M
    v = 0
    for i in range(N):
        if (bit>>i) & 1 == 1:
            for j in range(M):
                r[j] += CA[i][j+1]
            v += CA[i][0]
    if all([X <= ri for ri in r]):
        vm = min(vm, v)
if vm == float('inf'):
    print(-1)
else:
    print(vm)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    N, M, X = map(int, input().split())
    ans = 10 ** 9
    C_list = []
    A_list = []
    for _ in range(N):
        CA = list(map(int, input().split()))
        C_list.append(CA[0])
        A_list.append(CA[1:])
    for bit in range(2**N):
        cost = 0
        A = [0 for _ in range(M)]
        clear = True
        for i in range(N):
            if bit & 1<<i:
                cost += C_list[i]
                for j in range(M):
                    A[j] += A_list[i][j]
        for k in range(M):
            clear = clear and (A[k] >= X)
        if clear:
            ans = min(ans, cost)
    if ans == 10 ** 9:
        ans = -1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

p = []
books = []

for _ in range(N):
    tmp = list(map(int, input().split()))
    p.append(tmp[0])
    books.append(np.array(tmp[1:]))

saiyou = 0b00
ans = 10**7
for _ in range(2**N):
    mon = 0
    sat = np.zeros(M)
    for j, book in enumerate(books):
        if (saiyou >> j)&1 == 1:
            mon += p[j]
            sat += book
    if np.min(sat) >= X and ans > mon:
        ans = mon
    saiyou += 1

if ans == 10**7:
    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=13*pow(10,5)

for i in range(pow(2,N)):
    judge=str(bin(i))[2:].rjust(N,"0")
    #print(judge)
    cost=0
    li=[0]*M
    for j,s in enumerate(judge):
        if s=="1":
            cost+=CA[j][0]
            for k,a in enumerate(CA[j][1:]):
                li[k]+=a
    #print(li)
    if min(li)>=X:
        ans=min(ans,cost)
if ans==13*pow(10,5):
    ans=-1
print(ans)

Submission status: Accepted

Solution code:
N,M,X = [int(v) for v in input().split()]
abc = []

for _ in range(N):
    abc.append([int(v) for v in input().split()])


L = []
def dfs(index,c_L):
    if index == N:
        L.append(c_L)
        return
    dfs(index+1,c_L)
    n_L = c_L[:]
    n_L.append(abc[index])
    dfs(index+1,n_L)

dfs(0,[])

ans = float("inf")

for l in L:
    m = [0 for _ in range(M)]
    cost = 0
    for row in l:
        cost += row[0]
        for i,a in enumerate(row[1:]):
            m[i] += a

    flag = True
    for i in m:
        if i < X: flag = False
    if flag: ans = min(cost,ans)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

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

bit = []
for i in range(0, 2 ** N):
    pre_bit = []
    for k in range(N):
        pre_bit.append(i % 2)
        i = i // 2
    bit.append(pre_bit)

mi = 10 ** 7
for i in range(2 ** N):
    current = [0] * M
    okane = 0
    flag = 0
    for j in range(N):
        if bit[i][j] == 1:
            okane += CA[j][0]
            for k in range(M):
                current[k] += CA[j][k + 1]
    for i in range(M):
        if current[i] < X:
            flag = 1
    if flag == 0:
        if okane < mi:
            mi = okane

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

Submission status: Accepted

Solution code:
def main():
    n, m, x = tuple([int(e) for e in input().split()])
    matrix = []
    book_cost = []
    for i in range(n):
        arr = [int(e) for e in input().split()]
        book_cost.append(arr[0])
        matrix.append(arr[1:])

    best = float('inf')
    for i in range(1, (1 << n)):
        sm = [0] * m
        cost = 0
        for j in range(0, n):
            if (i >> j) & 1 > 0:
                for k in range(m):
                    sm[k] += matrix[j][k]
                cost += book_cost[j]
        if min(sm) >= x and cost < best:
            best = cost
    if best == float('inf'):
        print('-1')
    else:
        print(best)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N , M ,X = map(int,input().split())
L = []
for _ in range(N):
    l = list(map(int,input().split()))
    L.append(l)
ans = []
for i in range(2 ** N):
    rikai = [0 for _ in range(M)]
    cost = 0
    for b in range(N):
        if i  & (1 <<  b):
            for x in range(1,M + 1):
                rikai[x-1] += L[b][x] 
            cost += L[b][0]
    for x in rikai:
        if x < X: break
    else:
        ans.append(cost)
try:
    print(min(ans))
except:
    print(-1)

Submission status: Accepted

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


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


ans = 100000000

for i in range(2 ** n):
    kin = 0
    rikai = [0] * m
    for j in range(n):
        if ((i >> j) & 1):
            kin += ca[j][0]
            for k in range(m):
                rikai[k] += ca[j][k+1]
        if hantei(rikai):
            if kin < ans:
                ans = kin

if ans == 100000000:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
import copy

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


def make(x):
    global N

    bin_x=str(bin(x))[2:]
    rest=N-len(bin_x)
    bin_x=(bin_x[::-1]+'0'*(max(0,rest)))[::-1]

    return bin_x


cost=-1
for number in range(2**N):
    letter=make(number)
    develop=[0]*M
    temp=0
    for index in range(len(letter)):
        if letter[index]=='1':
            temp+=A[index][0]
            for j in range(1,M+1):
                develop[j-1]+=A[index][j]
    
    if X<=min(develop):
        if cost>=0:
            cost=min(cost,temp)
        else:
            cost=temp

print(cost)

Submission status: Accepted

Solution code:
def get_buy(i, N):
    ans = [0]*(N)
    for ind in range(N):
        if i % 2 == 1:
            ans[ind] = 1
        i //= 2
    return ans

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

ans = -1
for i in range(2**N):
    buy = get_buy(i, N)

    algorithm = [0]*M
    for j in range(N):
        if buy[j] == 1:
            for k in range(M):
                algorithm[k] += CA[j][k+1]
    
    ok = 1
    for j in range(M):
        if algorithm[j] < X:
            ok = 0

    # cost = 0
    # for j in range(N):
    #     if buy[j] == 1:        
    #         cost += CA[j][0]
    # print(buy, cost)
    # if cost == 1067:
    #     print("here")

    if ok == 1:
        cost = 0
        for j in range(N):
            if buy[j] == 1:        
                cost += CA[j][0]
        # print(buy, cost)
        if ans != -1:
            ans = min(ans, cost)
        else:
            ans = cost

print(ans)

Submission status: Accepted

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

for i in range(2**n):
    ans=[0]*m
    res=0
    for j in range(n):
        if not (i & (1<<j)):
            continue
        s=l[j]
        c=s[0]
        for k in range(m):
            ans[k]+=s[k+1]
        res+=c
    for i in range(m):
        if ans[i]<x:
            break
    else:
        money.append(res)
if money:
  print(min(money))
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections

def judge(li):
    algo = [0]*(m)
    cost = 0
    for i in range(len(li)):
        if li[i] == False:
            continue
        cost += C[i]
        for j in range(len(A[i])):
            algo[j] += A[i][j]
    for i in range(len(algo)):
        if algo[i]<x:
            return False
    return cost
n,m,x = map(int,input().split())
C = []
A = []
for i in range(n):
    d = list(map(int,input().split()))
    C.append(d[0])
    b = []
    for j in range(1,len(d)):
        b.append(d[j])
    A.append(b)
ans = 10000000000000
for i in range(2**n):
    li = [False]*n
    for j in range(n):
        if (i>>j)&1:
            li[n-j-1] = True
    a = judge(li)
    if a != False:
        ans = min(ans,a)
if ans == 10000000000000:
    print(-1)
else:
    print(ans)