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 copy
s = input().split()

n = int(s[0])
m = int(s[1])
x = int(s[2])

s_list = [[0 for i in range(m+1)] for j in range(n)]

for i in range(n):
    r = input().split()
    s_list[i][0] = int(r[0])
    for j in range(1,m + 1):
        s_list[i][j] = int(r[j])


gen = [0] * (m + 1)
kakaku = -1

for i in range(2 ** n):
    k = i
    kari = copy.copy(gen)
    for j in reversed(range(n)):
        if k >= 2 ** j:
            k -= 2 ** j
            for l in range(m+1):
                kari[l] += s_list[j][l]

    check = 0
    for j in range(1,m + 1):
        if kari[j] < x:
            check = 1
            break
    if check == 0 and (kari[0] < kakaku or kakaku == -1):
        kakaku = kari[0]

print(kakaku)

Submission status: Accepted

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

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n, m, x = map(int, input().split())
l = []
for i in range(n):
    l.append(list(map(int, input().split())))
#print(l)
ans = []
mon = [0]*(2**n)

def ok(anss,x):
    for i in range(len(anss)):
        if anss[i]<x:
            return False
    return True

for i in range(2**n):
    #print(bin(i))
    #print(anss, mon)
    anss=[0]*m
    for j in range(n):
        #print(l[j][0])
        #print(i-2**(n-1))
        if ((i >> j) & 1):
            mon[i] += l[j][0]
            for k in range(1,m+1):
                anss[k-1]+=l[j][k]
    #print(anss)
    if ok(anss,x):
        #print(ans)
        ans.append(mon[i])
#print(mon,ans)
if ans != []:
    print(min(ans))
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
a=[list(map(int,input().split()))for i in range(n)]
ans=[]
for bit in range(1<<n):
  total=0
  skill=[0]*m
  for i in range(n):
    if bit & (1<<i):
      total+=a[i][0]
      for j in range(m):
        skill[j]+=a[i][j+1]
  if all([k>=x for k in skill]):
    ans.append(total)
print(min(ans) if len(ans)!=0 else -1)

Submission status: Accepted

Solution code:
nmx=list(map(int, input().split()))
N=nmx[0]
M=nmx[1]
X=nmx[2]
ls=[input().split() for i in range(N)]
flg=False
alist=[[0 for p in range(M)] for q in range(2**N)]#全部の場合、2^N通りの成熟度をここに入れたい
clist=[0]*2**N #全部の場合の金額
for k in range(2**N):
    for i in range(N):
        if (k>>i) & 1:
            c=int(ls[i][0])
            clist[k]+=c
            for j in range(M):
                a=int(ls[i][j+1])
                alist[k][j]+=a
    if min(alist[k])<X:
        clist[k]=12*10**5+1
    else:
        flg=True
if flg:
    clist.sort()
    print(clist[0])
else:
    print('-1')

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0] * N
A = [0] * N
AA = [list(map(int, input().split())) for i in range(N)]
# 金額と理解度を分ける
for i in range(len(AA)):
    C[i] = AA[i][0]
    A[i] = AA[i][1:]
# -1判定のために
ans = sum(C) + 1
# 2**n で全パターン探索数となる
for p in range(2 ** N):
    Y = [0] * M
    cnt = 0
    for i, c in enumerate(C):
        if p % 2 == 1:
            cnt += c
            for j, a in enumerate(A[i]):
                Y[j] += a
        p //= 2
        # ループ数に対して毎回2を割り、その数の余りを1か0の判定を行うと全パターンとできる
        # 1となったものの理解度と金額を足し上げていく
    # M 数のうち最小値がX以上であれば金額をansに入れる
    ans = min(ans, cnt) if min(Y) >= X else ans
print(ans if ans <= sum(C) else -1)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0] * N
A = [0] * N
AA = [list(map(int, input().split())) for i in range(N)]
for i in range(len(AA)):
    C[i] = AA[i][0]
    A[i] = AA[i][1:]
ans = sum(C) + 1
for p in range(2 ** N):
    Y = [0] * M
    cnt = 0
    for i, c in enumerate(C):
        if p % 2 == 1:
            cnt += c
            for j, a in enumerate(A[i]):
                Y[j] += a
        p //= 2
    ans = min(ans, cnt) if min(Y) >= X else ans
print(ans if ans <= sum(C) else -1)

Submission status: Accepted

Solution code:
INF = float("inf")

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

ans = INF
for i in range(2 ** N):
    B = [0] * M
    S = 0
    for j, (c, *a) in enumerate(A):
        if (i >> j) & 1:
            S += c
            for k, ak in enumerate(a):
                B[k] += ak
    if all(b >= X for b in B):
        ans = min(ans, S)

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

Submission status: Accepted

Solution code:
def solve(i, cost, know, x, a):
    global res
    if i == len(a):
        for j in range(m):
            if know[j] < x:
                return
        res = min(res, cost)
        return
    solve(i + 1, cost, know, x, a)
    for j in range(m):
        know[j] += a[i][j + 1]
    solve(i + 1, cost + a[i][0], know, x, a)
    for j in range(m):
        know[j] -= a[i][j + 1]
n, m, x = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for j in range(n)]
know = [0] * (m)
res = 10 ** 7
solve(0, 0, know, x, a)
print(res if res != 10 ** 7 else - 1)

Submission status: Accepted

Solution code:
nmx=list(map(int, input().split()))
N=nmx[0]
M=nmx[1]
X=nmx[2]
mylist=[]
for i in range(N):
    mylist.append(list(map(int, input().split())))
Ans=100000*12+1
for i in range(2**N):
    A=[0]*M
    C=0
    for j in range(N):
        if (i>>j) & 1:
            C+=mylist[j][0]
            for k in range(M):
                A[k]+=mylist[j][k+1]
    if min(A)>=X:
        Ans=min(Ans, C)
if Ans==100000*12+1:
    print(-1)
else:
    print(Ans)

Submission status: Accepted

Solution code:
nmx=list(map(int, input().split()))
N=nmx[0]
M=nmx[1]
X=nmx[2]
mylist=[]
for i in range(N):
    mylist.append(list(map(int, input().split())))
Ans=100000*12+1
for i in range(2**N):
    A=[0]*M
    C=0
    for j in range(N):
        if (i>>j) & 1:
            C=C+mylist[j][0]
            for k in range(M):
                A[k]=A[k]+mylist[j][k+1]
    if min(A)>=X:
        Ans=min(Ans, C)
if Ans==100000*12+1:
    print(-1)
else:
    print(Ans)

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:
import itertools
import numpy as np

N, M, X = map(int, input().split())
C = []
H = []
for i in range(N):
    tmp = [int(x) for x in input().split()]
    H.append(tmp)

# print(H)

for i in range(2 ** N):
    cost = []
    for j in range(N):
        if bin(i).replace("0b", "").zfill(N)[j] == "1":
            cost.append(H[j])
            # combined1 = [x + y for (x, y) in zip(H[j], H[])]

    cost = np.array(cost)
    cost = cost.reshape(-1, M + 1)
    cost = np.sum(cost, axis=0)
    # print(cost.shape)
    C.append(list(cost))

# print(C)
result = []
for i in C:
    flag = True
    for j in range(M):
        if i[j + 1] >= X and flag:
            flag = True
        else:
            flag = False
    if flag:
        result.append(i[0])

if len(result) == 0:
    print(-1)
else:
    print(min(result))
# l = list(range(1, M + 1))
# hoge = itertools.combinations_with_replacement(l, N)
# for v in hoge:
#     print(v)

Submission status: Accepted

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

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

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

cost = 10 ** 8
for i in range(2 ** N):
    bit = []
    for j in range(N):
        if ((i >> j) & 1) == 1:
            bit.append(p[j])

    t = [0] * M
    for m in range(M):
        c = 1
        for n in bit:
            t[m] += lst[n][m]
        if t[m] < X:
            c = 0
            break
    co1 = 0
    if c:
        for n in bit:
            co1 += C[n]
        if co1 <= cost:
            cost = co1

if cost ==  10 ** 8:
    cost = -1

print(cost)

Submission status: Accepted

Solution code:
from itertools import product
import numpy as np

N, M, X = list(map(int, input().split()))
INF = 10**5 * 12 + 1
books = np.array([list(map(int, input().split())) for i in range(N)])
ans = INF
for selection in product([0, 1], repeat=N):
    selection = np.array(selection).reshape(N, 1)
    res = (books * selection).sum(axis=0)
    if min(res[1:]) >= X:
        ans = min(ans, res[0])
print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,M,X = map(int, readline().split())
data = np.array(read().split(), np.int64)
data = data.reshape(N,-1)
C = data[:,0]
A = data[:,1:]

cost = np.zeros(1<<N, np.int64)
ability = np.zeros((1<<N, M), np.int64)

for i in range(N):
  cost[1<<i:1<<(i+1)] = cost[:1<<i] + C[i]
  ability[1<<i:1<<(i+1)] = ability[:1<<i] + A[i]

ok = np.all(ability >= X, axis=1)

x = cost[ok]
answer = -1 if len(x) == 0 else x.min()
print(answer)

Submission status: Accepted

Solution code:
def dec_bin(num, n):
    ret = ""
    while num > 0:
        ret += str(num%2)
        num //= 2
    curr_len = len(ret)
    for i in range(0, n-curr_len):
        ret += '0'
    return ret[::-1]

min_cost = 100000000
nmx = [int(s) for s in input().split()]
n, m, x = nmx[0], nmx[1], nmx[2]
data = []
for i in range(n):
    row = [int(s) for s in input().split()]
    data.append(row)
for num in range(0, (1<<n)):
    dec = dec_bin(num, n)
    tot_cost = [0 for x in range(m)]
    price = 0
    for j in range(n):
        if dec[j] == '1':
            price += data[j][0]
            for i in range(m):
                tot_cost[i] += data[j][i+1]
    good = True
    for cost in tot_cost:
        if cost < x:
            good = False
            break
    #print(dec, tot_cost, price)
    if good:
        min_cost = min(price, min_cost)
if min_cost == 100000000:
    print(-1)
else:
    print(min_cost)

Submission status: Accepted

Solution code:
# AtCoder
N, M, X = map(int, input().split())
A = []
c = []

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

inf = 10**9
ans = inf

for s in range(1 << N):
    un = [0]*M
    price = 0
    for i in range(N):
        if (s >> i) % 2 == 0:
            continue
        price += c[i]
        for j in range(M):
            un[j] += A[i][j]

    ok = True
    for j in range(M):
        if un[j] < X:
            ok = False
    if ok:
        ans = min(ans, price)

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

def bit_search(a, n, m, x):
    min_price = np.inf
    for i in range(2 ** n):
        price = 0
        skill = np.zeros((n, m))
        for j in range(n):
            if (i >> j) & 1:
                price += a[j][0]
                skill[j] = a[j][1:]
        skill_sum = np.sum(skill, axis=0)\
                        if skill.shape[0] > 1 else skill
        if not (skill_sum >= x).all() or price > min_price: continue
        min_price = price
    return  min_price

def main():
    readline = stdin.readline
    n, m, x = map(int, readline().split())
    a = [list(map(int, readline().split())) for _ in range(n)]
    min_price = bit_search(a, n, m, x)
    return print('-1' if np.isinf(min_price) else  min_price)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

#print(a,c)

ans = 10 ** 8

for i in range(1 << n):
    cost = 0
    check = True
    d = [0 for i in range(m)]
    for j in range(n):
        if i >> j & 1:
            cost += c[j]
            for i2 in range(m):
                d[i2] += a[j][i2]
            #print(i >> j,d)
    for k in range(m):
        if d[k] < x:
            check = False
    if check:
        ans = min(ans, cost)
    #print(d,cost,check)
    
if ans == 10 ** 8:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

def bit_search(a, n, m, x):
    res = []
    for i in range(2 ** n):
        price = 0
        skill = np.zeros((n, m))
        for j in range(n):
            if (i >> j) & 1:
                price += a[j][0]
                skill[j] = a[j][1:]
        skill_sum = np.sum(skill, axis=0)\
                        if skill.shape[0] > 1 else skill
        if (skill_sum >= x).all(): res.append(price)
    return res

def main():
    readline = stdin.readline
    n, m, x = map(int, readline().split())
    a = [list(map(int, readline().split())) for _ in range(n)]
    res = bit_search(a, n, m, x)
    print('-1' if not res else min(res))
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = float('inf')
for j in range(1<<N):
    curr = 0
    score = [0] * M
    for k in range(N):
        if 1<<k & j :
            curr += C[k]
            for m in range(M):
                score[m] += A[k][m]
                
    if min(score) >= X:
        ans = min(curr, ans)

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

Submission status: Accepted

Solution code:
from itertools import product

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

INIT = 10**10
ans = INIT
pat = list(product([0, 1], repeat=n))

for p in pat:
    a_val = [0] * m
    c_yen = 0

    for i in range(n):
        if p[i] == 1:
            c_yen += c[i]
            for j in range(m):
                a_val[j] += a[i][j]

    flag = True
    for i in range(m):
        if a_val[i] < x:
            flag = False
            break
    if flag:
        ans = min(ans, c_yen)

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

Submission status: Accepted

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

for i in range(n):
    l = [int(_) for _ in input().split()]
    c[i]=l[0]
    for j in range(m):
        a[i][j] = l[j+1]

inf=float('inf')
ans=inf
for i in range(2 ** n):
    cost = 0
    d=[0]*m
    for j in range(n):
        if i >> j & 1:
            cost += c[j]
            for k in range(m):
                d[k] += a[j][k]

    ok = True
    for y in range(m):
        if d[y] < x:
            ok = False
    if ok:
        ans = min(ans, cost)
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0] * N
A = [list() for _ in range(N)]
for i in range(N):
    C[i], *A[i] = map(int, input().split()) #*は残りをAにinputの意味

def F(p):
    cost = 0
    rikais = [0] * M
    for i in range(N):
        if (p >> i) & 1:
            cost += C[i]
            for t in range(M):
                rikais[t] += A[i][t]
    return rikais, cost

ans = float("inf")
for p in range(2 ** N):
    rikais, cost = F(p)
    all_clear = True
    for r in rikais:
        if r >= X:
            continue
        if r < X:
            all_clear = False
    if all_clear:
        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 = [list(map(int, input().split())) for _ in range(n)]

ans = float("inf")
for i in range(2**n):
    l = [0] * m
    c = 0
    for j ,d in enumerate(format(i, "b").zfill(n)):
        f = 0
        if d == "1":
            c += ca[j][0]
            for k in range(1, m+1):
                l[k-1] += ca[j][k]
            
    for li in l:
        if li < x:
            f = 1
            break
    if f:
        continue
    ans = min(ans, c)

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

Submission status: Accepted

Solution code:
import numpy as np
# dfsで全探索
n, m, x = map(int, input().split())
c = []
a = np.zeros((n, m))
for i in range(n):
    ll = list(map(int, input().split()))
    c.append(ll[0])
    a[i] += np.array(ll[1:])
    

ans = float("INF")
# 0: Not Buy 1: Buy
s = []

def dfs(s):
    global ans
    if len(s) == n:
        r = np.zeros(m)
        ra = 0
        for j, k in enumerate(s):
            if k == 0:
                continue
            r += np.array(a[j])
            ra += c[j]
        if min(r) >= x:
            ans = min(ans, ra)
        return
    b = s.copy()
    nb = s.copy()
    b.append(0)
    nb.append(1)
    dfs(b)
    dfs(nb)

dfs([])
if ans == float("INF"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import product
def main():
    n, m, x = map(int, input().split())
    books = []
    for _ in range(n):
        books.append(tuple(map(int, input().split())))

    books_set_all = []
    books_pattern = product((0, 1), repeat=n)
    for each_pattern in books_pattern:
        books_set = [0] * (m + 1)
        for i1 in range(n):
            if each_pattern[i1] == 1:
                for i2 in range(m + 1):
                    books_set[i2] += books[i1][i2]
        books_set_all.append(books_set)
    price_all = []
    for ebs in books_set_all:
        price = ebs[0]
        ebs[0] = x
        if len([j for j in ebs if j >= x]) == m + 1:
            price_all.append(price)
    if len(price_all) > 0:
        print(min(price_all))
    else:
        print(-1)

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**10
for i in range(2 ** n):
         tmp = [0] * (m+1)
         price = 0
         for j in range(n):
                  if (( i >> j ) & 1 ) == 1:
                           for k in range(m+1):
                                    tmp[k] += ca[j][k]
         for l in range(1,m+1):
                  if tmp[l] < x:
                           break
         else:
                  if ans > tmp[0]:
                           ans = tmp[0]
if ans == 10**10:
         print(-1)
else:
         print(ans)

Submission status: Accepted

Solution code:
n,m,x = map(int,input().split())
cc = []
aa = []
for _ in range(n):
    c,*a = [int(i) for i in input().split()]
    cc.append(c)
    aa.append(a)
ans = 10**18
for i in range(2**n):
    ri = [0]*m
    co = 0
    for j in range(n):
        if (i>>j) & 1 == 1:
            co += cc[j]
            for k in range(m):
                ri[k] += aa[j][k]
                
    for j in ri:
        if j < x:
            break
    else:
        ans = min(ans,co)
        
if ans == 10**18:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
# ABC167 C

def main():
    n, m, x = map(int, input().split())
    List = []
    
    for _ in range(n):
        tmp = list(map(int, input().split()))
        List.append(tmp)

    minCost = 10**20

    for i in range(1, 2**n):
        #inBit = bin(i)[2:][::-1]
        inBit = ''.join(['{:0', str(n), 'b}']).format(i)[::-1]
        knowledge = [0 for _ in range(m)]
        cost = 0

        for bit in range(len(inBit)):
            if inBit[bit] == '1':
                cost += List[bit][0]
                for j in range(m):
                    knowledge[j] += List[bit][j+1]
        
        requirement = [a >= b for (a, b) in zip(knowledge, [x for _ in range(m)])]
        
        if False not in requirement and cost < minCost:
            minCost = cost
    
    if minCost == 10**20:
        print(-1)
    else:
        print(minCost)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

a_list = list()
c_list = list()

INF = 1001001001

for i in range(0, n):
    tmp = list(map(int, input().split()))
    c = tmp.pop(0)
    c_list.append(c)
    a_list.append(tmp)

ans = INF

for s in range(0, 1 << n):
    cost = 0
    d = [0]*m
    for i in range(0, n):
        if s >> i & 1:
            cost += c_list[i]
            for j in range(0, m):
                d[j] += a_list[i][j]
    ok = True
    for j in range(0, m):
        if d[j] < x:
            ok = False
    if ok:
        ans = min(ans, cost)

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

Submission status: Accepted

Solution code:
def main():
    n, m, x = map(int, input().split())
    books = []
    for _ in range(n):
        books.append(tuple(map(int, input().split())))

    books_set_all = []
    for bit in range(1<<n):
        books_set = [0] * (m + 1)
        for i in range(n):
            mask = 1 << i
            if bit & mask:
                for i2 in range(m + 1):
                    books_set[i2] += books[i][i2]
        books_set_all.append(books_set)
    price_all = []
    for ebs in books_set_all:
        price = ebs[0]
        ebs[0] = x
        if len([j for j in ebs if j >= x]) == m + 1:
            price_all.append(price)
    if len(price_all) > 0:
        print(min(price_all))
    else:
        print(-1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
n,m,x = map(int,input().split())
c_li = []
a_li = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    c_li.append(tmp[0])
    a_li.append(tmp[1:])
kumi = list(itertools.product([0,1], repeat=n))
ans_li = []
for each_kumi in kumi:
    each_li = [0]*m
    score = 0
    for i,k in enumerate(each_kumi):
        if k == 1:
            score += c_li[i]
            for j,kk in enumerate(a_li[i]):
                each_li[j] += kk
    flag = True
    for ea in each_li:
        if ea<x:
            flag = False
    if flag:
        ans_li.append(score)
if len(ans_li)==0:
    print(-1)
else:
    print(min(ans_li))

Submission status: Accepted

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

c=[]
a=[]

INF=1001001001
ans=INF

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

for i in range(1<<n):
  cost=0
  skill=[0 for _ in range(m)]
  for j in range(n):
    if (i>>j)&1==1:
      #print("i,j,(i>>j&1)",i,j,(i>>j&1))
      cost+=c[j]
      for k in range(m):
        skill[k]+=a[j][k]
  #print("skill",skill,"i",i)
  flag=True
  for j in range(m):
    if skill[j]<x:
      flag=False
      break
  if flag:
    ans=min(ans,cost)
if ans==INF:
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

def main():
    readline = stdin.readline
    n, m, x = map(int, readline().split())
    a = [list(map(int, readline().split())) for _ in range(n)]
    res = []
    for i in range(2 ** n):
        price = 0
        skill = []

        for j in range(1 << n):
            if ((i >> j) & 1) == 1:
                price += a[j][0]
                skill.append(a[j][1:])
        np_skill = np.array(skill)
        skill_sum = np.sum(np_skill, axis=0)\
                        if np_skill.shape[0] > 1 else np_skill

        if skill_sum.size != 0 and (skill_sum >= x).all():
            res.append(price)

    if not res: return print('-1')

    return print(min(res))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, X = map(int, input().split())
C = [0] * N
A = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
  A[i] = list(map(int, input().split()))
  C[i] = A[i][0]
  A[i] = A[i][1:]
ans = sum(C) + 1
Y = [0] * M
for p in range(2 ** N):
  for i in range(M):
    Y[i] = 0
  cnt = 0
  _p = p
  for i, c in enumerate(C):
    if _p % 2 == 1:
      cnt += c
      for j, a in enumerate(A[i]):
        Y[j] += a
    _p //= 2
  ans = min(ans, cnt) if min(Y) >= X else ans
print(ans if ans <= sum(C) else -1)

Submission status: Accepted

Solution code:
from math import *
from collections import *
from itertools import *
from bisect import *
from operator import *
import sys
sys.setrecursionlimit(1000000)
def io():
    return map(int,input().split())
def op():
    return list(map(int,input().split()))
def o():
    return int(input())
def kl(con,x=0):
    if x==0:print('Yes') if con else print('No')
    elif x==1:print('yes') if con else print('no')
    elif x==2:print('YES') if con else print('NO')
MOD =    1000000007
MAX=float('inf')
MIN=-float('inf')
p=input
# for _ in range(o()):
n,m,x=io()
cost=[0]*n
a=[0]*n
skill=[0]*m

for i in range(n):
    t=op()
    cost[i]=t[0]
    a[i]=t[1:]
ans=MAX
for i in range(1<<n):
    c=0
    skill=[0]*m
    for j in range(n):
        if (i>>j)&1:
            c+=cost[j]
            for k in range(m):
                skill[k]+=a[j][k]
    if min(skill) >= x:
        ans=min(ans,c)
if ans==MAX:print(-1)
else:print(ans)

Submission status: Accepted

Solution code:

import sys
from itertools import combinations

N,M,X = map(int,input().split())
CA = [list(map(int,input().split())) for _ in range(N)]
A=[0]*(M+1)

ans=0

for i in range(N):
    ans+=CA[i][0]
    for j in range(1,M+1):
        A[j]+=CA[i][j]


for i in range(1,M+1):
    if A[i] <X:
        print(-1)
        sys.exit()


for i in range(1,N+1):
    for e in combinations(range(N),i):
        c = 0
        A = [0]*M
        for f in e:
            c += CA[f][0]
            for j in range(M):
                A[j] += CA[f][j+1]
        if min(A) >= X:
            ans = min(ans,c)
        
else:
    print(ans)

Submission status: Accepted

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

C = []
A = []

for _ in range(N):
    CA = [int(x) for x in input().split()]
    C.append(CA[0])
    A.append(CA[1:])

INF = 99999999999999999999999
minC = INF

for i in range(1<<N):
    tmpC = 0
    tmpA = [0] * M
    for j in range(N):
        if i & (1 << j):
            tmpC += C[j]
            for k in range(M):
                tmpA[k] += A[j][k]

    if min(tmpA) >= X:
        minC = min(tmpC, minC)

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

Submission status: Accepted

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

n, m, x = map(int, input().split())
a = np.array([list(map(int, input().split())) for _ in range(n)], dtype = np.int32)
ans = sys.maxsize
for bit in product((False, True), repeat = n):
    row_sum = np.sum(a[np.where(bit)], axis = 0)
    if m == np.count_nonzero(row_sum[1:] >= x):
        ans = min(ans, row_sum[0])
print(-1 if ans == sys.maxsize else ans)

Submission status: Accepted

Solution code:
def main():
    N, M, X, *CA = map(int, open(0).read().split())
    C = [0]*N
    A = [[0]*M for i in range(N)]

    for i in range(N):
        C[i] = CA[(M + 1)*i]
        for j in range(M):
            A[i][j] = CA[(M + 1)*i + j + 1]
    # print(N, M, X, C, A)
    B = [0]*M
    for i in range(N):
        for j in range(M):
            B[j] += A[i][j]
    for i in range(M):
        if B[i] < X:
            print(-1)
            return

    ans = sum(C)
    for i in range(2**N):
        B = [0]*M
        price = 0
        for j in range(N):
            if (i >> j) & 1 == 1:
                price += C[j]
                for k in range(M):
                    B[k] += A[j][k]
        found = True
        for j in range(M):
            if B[j] < X:
                found = False
                break
        if found:
            ans = min(ans, price)
    print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

def main():
    readline = stdin.readline
    n, m, x = map(int, readline().split())
    a = [list(map(int, readline().split())) for _ in range(n)]
    res = []
    for i in range(2 ** n):
        price = 0
        skill = []

        for j in range(n):
            if ((i >> j) & 1):
                price += a[j][0]
                skill.append(a[j][1:])
        np_skill = np.array(skill)
        skill_sum = np.sum(np_skill, axis=0)\
                        if np_skill.shape[0] > 1 else np_skill

        if skill_sum.size != 0 and (skill_sum >= x).all():
            res.append(price)

    if not res: return print('-1')

    return print(min(res))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, x = map(int, input().split())
b = 10**18
tm = []
for i in range(n):
    tm.append(list(map(int, input().split())))
for i in range(2**n):
    c = [0 for i in range(m)]
    sum = 0
    for j in range(n):
        if (i >> j) & 1:
            sum += tm[j][0]
            for k in range(m):
                c[k] += tm[j][k+1]
    if min(c) >= x:
        b = min(b, sum)
if b == 10**18:
    print('-1')
else:
    print(b)

Submission status: Accepted

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

default = 10 ** 5 * 12 + 1
min_money = default

for bits in range(1 << N):
    money = 0
    algo = [0] * M
    for i in range(N):
        if bits >> i & 1 == 1:
            money += books[i][0]
            for j in range(M):
                algo[j] += books[i][j + 1]

    if min(algo) >= X:
        min_money = min(min_money, money)

print('-1' if min_money == default else min_money)

Submission status: Accepted

Solution code:
n,m,x=map(int,input().split())
b=[list(map(int,input().split())) for _ in range(n)]
ans = 100000000
for i in range(1<<n):
    money = 0
    s=[0]*m
    for j in range(n):
        if(i>>j)&1:
            money +=b[j][0]
            for k in range(1,m+1):
                s[k-1]+=b[j][k]
    if min(s)>=x:
        ans=min(ans,money)
if ans != 100000000:
    print(ans)
else:
    print(-1)